Ronzii's Blog

Just your average geek's blog

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

\begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix}^n =        \begin{pmatrix} F_{n+1} & F_n \\                        F_n     & F_{n-1} \end{pmatrix}.

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]);
}
About these ads

July 9, 2011 - Posted by | C++ | , , ,

4 Comments »

  1. Great post !!

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

  2. excellent article :)

    Comment by jhamb | March 29, 2012 | Reply

  3. nice one sir :-) … dceits rocks !!

    Comment by joker | April 22, 2012 | Reply

  4. Awesome

    Comment by Ganesan | June 21, 2012 | Reply


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

Join 31 other followers