Python vs PHP speed

Question

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.

Answer 1

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.

Answer 2

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.

Answer 3

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.

Answer 4

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.