Python vs PHP speed

I want to solve a problem from Project Euler (BTW, problem 25), and I found a solution in Python:

fibonacci = 1
old1 = 0
old2 = 1
limit = 1000

i = 1

while len(str(fibonacci)) < limit:
    fibonacci = old1 + old2
    old1 = old2
    old2 = fibonacci
    i = i + 1

print(i)

It took 1.5 seconds to calculate.

I implemented the same in PHP, this is the code:

$fibonacci = 1;
$old1 = 0;
$old2 = 1;
$limit = 1000;

$i = 1;

while (strlen((string)$fibonacci) < $limit){
    $fibonacci = $old1 + $old2;
    $old1 = $old2;
    $old2 = $fibonacci;
开发者_如何学编程    $i = $i + 1;
}
print($i);

And it took more than 30 minutes, and still calculating...

I know that Python is considered faster than PHP, but still it shouldn't be so big a difference. How to improve my PHP code to get the results faster, if there is a way to do it?

EDIT:

I edit this post based on comments below so first my solution was not going to work. One solution can be instead of old while to put this one:

while (strlen(number_format($fibonacci, 0, '', '')) < $limit){ ... }

But again is a big speed issue.

So the final solution is using BCMath:

$fibonacci = '1';
$old1 = '0';
$old2 = '1';
$limit = 1000;

$i = 1;

while (strlen($fibonacci) < $limit){

    $fibonacci = bcadd($old1, $old2);
    $old1 = $old2;
    $old2 = $fibonacci;
    $i = $i + 1;
}
echo $fibonacci . "<br />";
print($i);

So you can get the results at the same speed as Python in PHP.

Definitely, the PHP is going into an infinite loop. There's no way it could be taking that long if there wasn't something wrong...

I don't think counting the digits of these numbers with strlen is going to work in PHP. PHP is dealing with the numbers in scientific notation, in lower precision than Python.

I added debugging echo statements to PHP, to print out $fibonacci and $i for each step.

A typical Python line looks like

fib is 7540113804746346429
i is 92

In PHP, that's

fib is 7.54011380475E+18
i is 92

To accomplish this in PHP, you'll probably need to use a higher precision math library.

Check out http://www.php.net/manual/en/book.bc.php - you can use the bcadd function to accomplish the addition, and it will work as it does in Python.

It isn't a speed issue, it's a logic problem in the while condition for termination.

It's probably not going to finish. When you convert the current value of $fibonacci to a string in your while test, it will be converted to scientific format and truncated to a limited set of decimal places (dependent on your precision setting) when you cast it to string. That number of digits will be a lot less than 1000, so the while termination condition won't ever be met.

The problem is, that you are working with big numbers. You should use BC Math Functions (php.net/bc). So your code can be:

$fibonacci = "1";
$old1 = "0";
$old2 = "1";
$limit = 1000;

$i = 1;

while (strlen($fibonacci) < $limit){
    $fibonacci = bcadd($old1, $old2);
    $old1 = $old2;
    $old2 = $fibonacci;
    $i = $i + 1;
}
print($i);

I have tried it and it takes about 0.095s.

Many of project Euler problems will have to handle big numbers. PHP will make your big numbers look like 2.579234678963E+12 which is the Exponential representation of the number... It's obviously hard to work with. So, for most of problems, it's best to go with BCMath Functions. This will keep your number as it is, even if it is a giant number.

Note that using echo bcmul(500,500); will never be as fast as echo 500*500. And, BCMath function return values are always strings.

To fix your problem replace all arithmetic operations with the corresponding BCMath function.

I optimized a bit the Python code. Using len(str()) to check the number of digits is very slow. Replaced by math.log10 run your program much faster

The first term in the Fibonacci sequence to contain 1000 digits is : 4782 Calculated in 0.008573 seconds

import time
from math import log10


def digits(n): # Return the number of digits for n>=1
    return int(log10(n))+1

fibonacci = 1L # Thanks to Python to handle very big numbers
old1 = 0
old2 = 1
limit = 1000

i = 1


start = time.time() #Start timer for bench
while digits(fibonacci) < limit:
    fibonacci = old1 + old2
    old1 = old2
    old2 = fibonacci
    i +=  1



print "The first term in the Fibonacci sequence to contain %s digits is : %s" % (str(limit), str(i))

print "Calculated in %3.6f seconds" %  (time.time() - start)

Since the problem seems to be with converting to strings, here's a much faster way to do it that doesn't require it. This is essentially the same algorithm as you have posted (so I don't feel bad showing it to you) but demonstrates how to use division to test the length of an integer instead of converting it to a string.

def fibonacci_digits(limit):
    limit = 10**limit
    fib = 1
    old1 = 0
    old2 = 1

    i = 1
    size = 1
    while size < limit:
        fib = old1 + old2
        if not size//fib:  # // is pythons integer division operator, not a comment
            size *= 10
        old1 = old2
        old2 = fib
        i += 1

    return i

print fibonacci_digits(1000)

Converting to a string is slow and is almost never the right thing to do. Here's the timeit results:

$ python -mtimeit -s'import fib' 'fib.fibonacci_digits(1000)'
10 loops, best of 3: 30.2 msec per loop

$ python -mtimeit -s'import fib' 'fib.fibonacci_digits2(1000)'
10 loops, best of 3: 1.41 sec per loop