Program for Fibonacci numbers | GeeksforGeeks

Write a function int fib(int n) that returns . 
Method 2 ( Use Dynamic Programming )

f[0] = 0;

  f[1] = 1;

 

  for (i = 2; i <= n; i++)

  {

      /* Add the previous 2 numbers in the series

         and store it */

      f[i] = f[i-1] + f[i-2];

  }

 

  return f[n];

Method 3 ( Space Otimized Method 2 )

int fib(int n)

{

  int a = 0, b = 1, c, i;

  if( n == 0)

    return a;

  for (i = 2; i <= n; i++)

  {

     c = a + b;

     a = b;

     b = c;

  }

  return b;

}

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

This another O(n) which relies on the fact that if we n times multiply the matrix M = {{1,1},{1,0}} to itself (in other words calculate power(M, n )), then we get the (n+1)th Fibonacci number as the element at row and column (0, 0) in the resultant matrix.

The matrix representation gives the following closed expression for the Fibonacci numbers:

Method 5 ( Optimized Method 4 )
The method 4 can be optimized to work in O(Logn) time complexity. We can do recursive multiplication to get power(M, n) in the previous method.

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 power() in method 4 */

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;

}

Read full article from Program for Fibonacci numbers | GeeksforGeeks