A blog about programming and more programming.

Fibonacci Numbers

with 5 comments

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.
using namespace std;

long long F[93];
long long Fib(int N)
if (N==1)
return 1;
if (N==0)
return 0;
if (F[(N+1)/2-1]==0)
if (F[(N+1)/2]==0)
if (N%2==0)

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

Subscribe to comments with RSS.

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


    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.


      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

Leave a Reply

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

You are commenting using your 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

%d bloggers like this: