# Duncan's blog

## October 6, 2014

### Project Euler: problem 25 (PHP) – 1000-digit Fibonacci number

Filed under: PHP,Project Euler — duncan @ 8:00 am

Photo courtesy of Anette Hallner

I previously blogged about this Project Euler puzzle nearly 6 years ago, using Python.  This is my approach using PHP as a simple practical exercise for myself, and I’d appreciate any feedback on my PHP code.

Problem 25:

The Fibonacci sequence is defined by the recurrence relation:

Fn = Fn-1 + Fn-2, where F1 = 1 and F2 = 1.

Hence the first 12 terms will be:

F1 = 1
F2 = 1
F3 = 2
F4 = 3
F5 = 5
F6 = 8
F7 = 13
F8 = 21
F9 = 34
F10 = 55
F11 = 89
F12 = 144

The 12th term, F12, is the first term to contain three digits.

What is the first term in the Fibonacci sequence to contain 1000 digits?

Here’s my code:

```<?php
\$fibonacci = 1;
\$old1 = 0;
\$old2 = 1;
\$limit = 1000;

\$i = 1;

\$limit = bcpow(10, \$limit-1);

while (bccomp(\$fibonacci, \$limit) == -1) {
\$fibonacci = bcadd(\$old1, \$old2);
\$old1 = \$old2;
\$old2 = \$fibonacci;
\$i++;
}

echo \$i;
```

Initially I took the same approach as with the Python, with the while loop checking the length of the string of the fibonacci value.  However this seemed to be way too slow for PHP to handle, even when I tried just going up to a value 100 characters long, never mind 1000 characters.

So I tried a slightly different technique:

• 10 ^ 2 = 100, length = 3.
• 10 ^ 3 = 1000, length = 4.
• In other words, 10 ^ x would have length of x + 1, and therefore 10 ^ 999 would have length 1000.

I used the BC Math functions for working with arbitrarily large numbers.   Firstly bcpow() to calculate 10 ^ 999 value as being the upper limit for our loop.  Then bccomp() to check if we’ve reached our limit.  And bcadd() to add the two increasingly-large values together to make our fibonacci values.  Seemed to work pretty fast after that.