## Fibonacci Numbers

Fibonacci Numbers are one of the most common sequence in maths and computer science. One of the question is how fast can you calculate Fib(N). The obvious time complexity to calculate this would be O(N) but thanks to late Prof. Edsgar W Dijkstra there exists an O(log N) solution. He gave this two equations :

F(2n-1) = F(n-1)^2 + F(n)^2 F(2n) = ( 2 F(n-1) + F(n) ) F(n)

I have written a program which implements it in time O(log N) but for simplicity reasons the space complexity is O(N). Also the program is capable of calculating the answers only till index 92 which is within the **long long** range. It sure can be implemented for big integers library.

#include

using namespace std;

long long F[93];

long long Fib(int N)

{

if (N==1)

return 1;

if (N==0)

return 0;

else

{

if (F[(N+1)/2-1]==0)

F[(N+1)/2-1]=Fib((N+1)/2-1);

if (F[(N+1)/2]==0)

F[(N+1)/2]=Fib((N+1)/2);

if (N%2==0)

return

((2*F[(N+1)/2-1]+F[(N+1)/2])*F[(N+1)/2]);

else

return

((F[(N+1)/2-1]*F[(N+1)/2-1]+

F[(N+1)/2]*F[(N+1)/2]));

}

}

int main()

{

int N;

while (scanf(“%d”,&N),N>=0&&N<93)
{
printf("%lld\n",Fib(N));
}
}[/sourcecode]
-fR0D

I heard about log n algo for fibonacci that uses matrix property. does dijkstra fibonacci uses different method?

gieSeptember 26, 2009 at 3:39 PM

No it is the same. Just that since these are recurrence relations, you can also write these equations in matrix form.

fR0DSeptember 26, 2009 at 7:58 PM

Hello….Thank you very much for this nice tutorial…..but i have a problem and i can’t solve it…please help me….the problem is determining f(n)=f(n-1)+f(n-3). how can i solve this using matrix properties…please….reply as soon as possible

Nafis IslamAugust 11, 2012 at 7:37 PM

Read this blog post: https://comeoncodeon.wordpress.com/2011/05/08/recurrence-relation-and-matrix-exponentiation/

fR0DDYAugust 11, 2012 at 10:57 PM

Thanks bro……..thank you so much….finally i understand how this works……

Nafis IslamAugust 12, 2012 at 11:41 PM