Algo #111: Nth Fibbonacci Number in log(n) complexity

Problem Statement:
   Find the Nth Fibbonaci number in log(n) complexity.

Download Source Code
Solution:

The recurrence Relation for the Fibonacci series given by
               f(n) = f(n-1) + f(n-2)

We can code up the Recursive and DP (Dynamic programming) Solution for the above equation, these techniques gives us a  exponential complexity and O(n) complexity respectively.

Recursive Solution:

int fib1(int n) {
   if(n<=1)
    return n;
   return fib1(n-1) + fib(n-2);
  }

Time Complexity: Exponential

Dynamic Programming Approach:

int fib2(int n)
 {
  if(n==0)
   return 0;
  int old1=0 , old2=1 , curr,i=2;
  for(;i<=n;i++)
  {
   curr = old1 + old2;
   old1= old2;
   old2 = curr;
  }
  return old2;
 }

Time Complexity: O(n)

Now we will discuss an approach which is of the order of  O(n)  and is called as Matrix Exponentiation.

Matrix Exponentiation is used to find the nth element of a series which can be represented in the form of a recurrence equation.

Now our recurrence equation can be represented in the form of Matrix multiplication

       f(n) = f(n-1) + f(n-2)

which can be represented as

| f(n)  |  =  I x  | f(n-1) |
| f(n-1)|          | f(n-2) |

where I = | a  b |
          | c  d |

Expanding and solving, we get

f(n) = a*f(n-1) + b*f(n-2)
and 
f(n-1) = c*f(n-1) + d*f(n-2)

solving we get,

I = | a  b |  =  | 1  1 |
    | c  d |     | 1  0 |

Our goal is to find [ f(n) f(n-1)] , from bottom to top by recursive doubling (Matrix exponentiation)

To get 
| f(n)   | = I x | f(n-1) |  , where I = | 1 1 |
| f(n-1) |       | f(n-2) |              | 1 0 |

We start with 

| f(2) | =  I x | f(1) |   , where | f(1) | = | 1 |
| f(1) |        | f(0) |           | f(0) |   | 1 |
then, 
| f(3) | =  I x | f(2) | = I^2 x | f(1) |
| f(2) |        | f(1) |         | f(0) |
then
| f(4) | =  I x | f(3) | = I^3 x | f(1) |
| f(3) |        | f(2) |         | f(0) |
...
...
...
| f(n)   | =  I x | f(n-1) | = I^(n-1) x | f(1) |
| f(n-1) |        | f(n-2) |             | f(0) |

You can observe that now we are left out with calculating I^(n-1) this is where matrix exponentiation will yield its result in O(log N) time.

Lets understand logic behind recursive doubling, which reduces the computation time to O(log N)

Now lets suppose we have to calulate I^n , 
If n is odd 
             I^n = I^((n-1)/2)  * I^((n-1)/2) * I 
If n is even 
             I^n = I^(n/2) * I^(n/2)

example 
   1. n = 9 (odd)
            I^9 = I^4 * I^4 * I

   2. n=12 (even)
             I^12 = I^6 * I^6

Now lets code up our logic.

private static int[][] F = { { 1, 1 }, { 1, 0 } }; // will change , capture rsult here
private static int[][] I = { { 1, 1 }, { 1, 0 } }; //will remain fixed
 
 public static int fib(int n){
  if(n==0)
   return 0;
  power(F,n-1);
  
  return F[0][0];
 }
 
 /**
  * Calculates F to the power n
  * @param F
  * @param n
  */
 private static void power(int[][] F, int n) {
  if(n==0 || n==1)
   return;
  
  power(F,n/2);
  multiplyMatrix(F,F);
  
  if(n%2!=0)
   multiplyMatrix(F, I);
 }
 
 /**
  * Multiples Matrixes of size 2X2
  */
 public static int[][] multiplyMatrix(int[][] A, int[][] B)
 {
    int x =  A[0][0]*B[0][0] + A[0][1]*B[1][0];
    int y =  A[0][0]*B[0][1] + A[0][1]*B[1][1];
    int z =  A[1][0]*B[0][0] + A[1][1]*B[1][0];
    int w =  A[1][0]*B[0][1] + A[1][1]*B[1][1];
   
    A[0][0] = x;
    A[0][1] = y;
    A[1][0] = z;
    A[1][1] = w;
    
    return A;
 }
 
 public static void main(String[] args) {
  //1,1,2,3,5,8,13,21,34,55,89...
  int n = 8;
  System.out.println(n + "--->" + fib(n));
 }

References:
1. CodeChef
2. Wikipedia

Please comment and post your suggestions.
Happy Coding !!