### Your best Fibonacci algorithm?

Posted:

**Thu Jul 15, 2010 3:58 pm UTC**Okay, I was wondering what you pplz here on the interwebz have as your fastest method of computing Fibonacci numbers - given a number N, return the Nth fibonacci number. A few simple ones I know:

if (N<3) {return 1;} else {return (fibo(N-1)+fibo(N-2));}

Based directly on the mathematical definition. If b is the number of bits in an int, runs in O(b*2^N). Sucks.

var a=1;

var b=1;

var t;

for (i=3; i<=N; i++){

t=b;

b=a;

a+=b;

}

return a;

A bit more efficient, and I guess it runs in (b*N). Not optimal, I guess...

The best one I've thought of exploits a certain property that Fibonacci numbers have:

Fibo(a)*Fibo(b)+Fibo(a+1)*Fibo(b+1)=Fibo(a+b+1)

So, first we compute the binary expansion of N. Then, we can use the above rule I just mentioned to compute the (2^A - 1) fibonacci numbers, where A is integer. To see this, suppose we know that Fibo(15)=610, Fibo(16)=987, and Fibo(17)=1597. Then, we can see that Fibo(31)=610*610+987*987=1346269 and Fibo(33)=987*987+1597*1597=3524578. Then, Fibo(32)=Fibo(33)-Fibo(31). We can use these three to find the next group of three fibonacci numbers. Once we have Fibo(2^floor(log_2(N))-1) computed, we can again "add" them in with the identity above, in a way corresponding to the binary expansion of N, to sum the indices to N.

Well, that's an outline of my most efficient algorithm. I forget what O() it runs in, but it was better than O(b*N). So, what do other people have? I'm eager to know!

if (N<3) {return 1;} else {return (fibo(N-1)+fibo(N-2));}

Based directly on the mathematical definition. If b is the number of bits in an int, runs in O(b*2^N). Sucks.

var a=1;

var b=1;

var t;

for (i=3; i<=N; i++){

t=b;

b=a;

a+=b;

}

return a;

A bit more efficient, and I guess it runs in (b*N). Not optimal, I guess...

The best one I've thought of exploits a certain property that Fibonacci numbers have:

Fibo(a)*Fibo(b)+Fibo(a+1)*Fibo(b+1)=Fibo(a+b+1)

So, first we compute the binary expansion of N. Then, we can use the above rule I just mentioned to compute the (2^A - 1) fibonacci numbers, where A is integer. To see this, suppose we know that Fibo(15)=610, Fibo(16)=987, and Fibo(17)=1597. Then, we can see that Fibo(31)=610*610+987*987=1346269 and Fibo(33)=987*987+1597*1597=3524578. Then, Fibo(32)=Fibo(33)-Fibo(31). We can use these three to find the next group of three fibonacci numbers. Once we have Fibo(2^floor(log_2(N))-1) computed, we can again "add" them in with the identity above, in a way corresponding to the binary expansion of N, to sum the indices to N.

Well, that's an outline of my most efficient algorithm. I forget what O() it runs in, but it was better than O(b*N). So, what do other people have? I'm eager to know!