Fibonacci Time Efficiency

(1 + sqrt(5)) ^ n - (1 - sqrt(5)) ^ n-------------------------------------              2 ^ n * sqrt(5)

^ indicates exponentiation

To elaborate on SiCrane's post:

Fibonacci numbers are related to the golden ration and its conjugate, which are both given by the following equations:

g = (1 + sqrt(5))/2
g_c = (1 - sqrt(5))/2

It can be shown (by induction) that the ith Fibonacci number is

F_i = (g^i - g_c^i)/(sqrt(5))

If you want to go iterative (ie dynamic programming):



or you could even do it recursively (ie memoization):



Memoization caches your results so that you never end up recomputing the same recursion subtree more than once.

Here's the best method I know of. If you have two consecutive Fibonacci numbers F(n) and F(n+1) as a column, you can multiply on the left by the matrix

(0 1)(1 1)

and you get

(0 1)   ( F(n) )   (   F(n+1)  )   (F(n+1))(1 1) * (F(n+1)) = (F(n)+F(n+1)) = (F(n+2))

The result of this operation is advancing from (F(n),F(n+1)) to (F(n+1),F(n+2)). We can start with (0,1) -which is (F(0),F(1))- and repeat this operation n times. What you get is the following formula:

(0 1)^n   (0)   ( F(n) )(1 1)   * (1) = (F(n+1))

The n-th power of the matrix can be computed in log(n) matrix multiplications, using a binary exponentiation method. You can also note that all the matrices you need have the following form:

(a  b )(b a+b)

You can see that the multiplication of two such matrices yields another matrix of the same type:

(a  b )   (x  y )   (  a*x+b*y      a*y+b*x+b*y   )(b a+b) * (y x+y) = (b*x+a*y+b*y 2*b*y+a*x+a*y+b*x)

So you can just do all the operations with a type like

This results in an algorithm that requires log(n) multiplications to compute F(n). Of course, instead of doubles, you can do the whole thing using some large integer class and the algorithm would still work.

A similar algorithm can be obtained by implementing a class that represents numbers in the field named Q[sqrt(5)], which consists of numbers that are of the form a+b*sqrt(5), where a and b are rationals.

Here's another method, good enough if you just want your result as doubles:

Of course, to reeeally get O(1) effeciency, you could precompute all of the values of the Fibonacci seqence you need. Not nice to extreme-memory-saving-devices, but for your typical household computer, you'd never know the difference, and it's instant.

Sometimes tradeoffs like this one are the best ;)

Thanks for the help people. I will try out the methods you've provided and see which one I like best in the flow of my program.

here for a O(1) algorithm:

const float sq5 = (float)sqrt(5.0f);
const float gold = (float)(sqrt(1.25f) + 0.5f);
int fibonacci(int n)
{
if (n < 0)
throw anErrorOrAnException();
return round(pow(gold, n) / sq5);
}

I know some function names are not right, but the algorithm is there...

round(x) == floor(x + 0.5f)

pow(x, y) means x ^ y

gold is the golden number...

Yes the number of recursive calls is logarithmic, but isn't the number of flops of order n?