**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 !!

## No comments:

## Post a Comment