COME ON CODE ON

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

Advertisements

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?

    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


Leave a Reply

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

WordPress.com Logo

You are commenting using your WordPress.com 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: