Fibonacci Numbers

Fibonacci is the most famous sequence in the programming world.
It is defined by the following recursive formulation:
f(n)=f(n-1) + f(n-2) where f(0)=0 & f(1)=1.
The first few numbers of the sequence are:
0,1,1,2,3,5,8,13,21,34,55……
Program to find the N-Th Fibonacci number can be implemented iteratively or recursively very easily.But,for large values of N,we need an optimized algorithm.

Using Recursion-

fib(n)
{
 if(n==0) return 0;
 if(n==1) return 1;
 return fib(n-1)+fib(n-2);
}

This has an exponential time complexity.

Using Iteration-

fib(n)
{
if(n==0) return 0;
if(n==1) return 1;
a=0;
b=1;
    for(i=2;i<=n;i++)
      {
        c=a+b;
        a=b;
        b=c;
       }
return b;
}    

This code has a time complexity of O(N).

Using power of the matrix{(0,0),(1,1)}-

If we n times multiply the matrix M = {{1,1},{1,0}} to itself,then we get the (n+1)th Fibonacci number as the element at row and column (0, 0) in the resultant matrix.

|1 1|^n = | F(n+1) F(n) |
|0 1|        | F(n)   F(n-1)|

Result of exponentiation can be calculated using this method in O(logn).

/* function that returns nth Fibonacci number */
int fib(int n)
{
  int F[2][2] = {{1,1},{1,0}};
  if(n == 0)
    return 0;
  power(F, n-1);
  return F[0][0];
}
 
/* Optimized version of calculating power*/
void power(int F[2][2], int n)
{
  if( n == 0 || n == 1)
      return;
  int M[2][2] = {{1,1},{1,0}};
 
  power(F, n/2);
  multiply(F, F);
 
  if( n%2 != 0 )
     multiply(F, M);
}
 
void multiply(int F[2][2], int M[2][2])
{
  int x =  F[0][0]*M[0][0] + F[0][1]*M[1][0];
  int y =  F[0][0]*M[0][1] + F[0][1]*M[1][1];
  int z =  F[1][0]*M[0][0] + F[1][1]*M[1][0];
  int w =  F[1][0]*M[0][1] + F[1][1]*M[1][1];
 
  F[0][0] = x;
  F[0][1] = y;
  F[1][0] = z;
  F[1][1] = w;
}

This code has a time complexity of O(logN).

Leave a Reply

Your email address will not be published. Required fields are marked *

*

* Copy This Password *

* Type Or Paste Password Here *

41,728 Spam Comments Blocked so far by Spam Free Wordpress

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>