## Using Matrix Exponentiation to calculate the Nth Fibonacci Number

Fibonacci numbers have always been interesting since ancient times. The initial puzzle that Fibonacci posed was: how many pairs of rabbits will there be in one year if all of them can mate with each other. There is also a problem on SPOJ related to this.

Now this is the **recursive** solution. As you can see there are a lot of calls to the function and has exponential time complexity.

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

**Dynamic Programming**

The time complexity of this solution is O(n).

int fib(int n) { int a = 1, b = 1,i; for (i = 3; i <n;i++) { int c = a + b; a = b; b = c; } return b; }

**Matrix Exponetiation**

Now, there is a method to calculate the nth fibonacci number in O(log(n)) time. For this you need the basics of matrix exponentiation. Check out the following matrix

The nth fibonacci number can be found using this matrix also if we apply repeated squaring to this matrix, the solution is reduced to O(log(n))

long long fibonacci(int n) { long long fib[2][2]= {{1,1},{1,0}},ret[2][2]= {{1,0},{0,1}},tmp[2][2]= {{0,0},{0,0}}; int i,j,k; while(n) { if(n&1) { memset(tmp,0,sizeof tmp); for(i=0; i<2; i++) for(j=0; j<2; j++) for(k=0; k<2; k++) tmp[i][j]=(tmp[i][j]+ret[i][k]*fib[k][j]); for(i=0; i<2; i++) for(j=0; j<2; j++) ret[i][j]=tmp[i][j]; } memset(tmp,0,sizeof tmp); for(i=0; i<2; i++) for(j=0; j<2; j++) for(k=0; k<2; k++) tmp[i][j]=(tmp[i][j]+fib[i][k]*fib[k][j]); for(i=0; i<2; i++) for(j=0; j<2; j++) fib[i][j]=tmp[i][j]; n/=2; } return (ret[0][1]); }

Great post !!

Comment by mosa@mosa.com | January 9, 2012 |

excellent article :)

Comment by jhamb | March 29, 2012 |

nice one sir :-) … dceits rocks !!

Comment by joker | April 22, 2012 |

Awesome

Comment by Ganesan | June 21, 2012 |