# COME ON CODE ON

A blog about programming and more programming.

## 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

Written by fR0DDY

February 24, 2009 at 1:56 PM

Posted in Maths, Programming

Tagged with , ,

### 5 Responses

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

gie

September 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.

fR0D

September 26, 2009 at 7:58 PM

2. 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 Islam

August 11, 2012 at 7:37 PM

• fR0DDY

August 11, 2012 at 10:57 PM

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

Nafis Islam

August 12, 2012 at 11:41 PM