Duncan's blog

October 6, 2014

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

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

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.

Advertisements

Leave a Comment »

No comments yet.

RSS feed for comments on this post. TrackBack URI

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Blog at WordPress.com.

%d bloggers like this: