Can anybody give me code snippet for finding the nth fibo number in logn time using matrix exponentiation ?

thanks in advance.

I_m_rude
Deleted Member

Check this out [Fibonacci](nth fibo number in logn time using matrix exponentiation).
But you must try it on your own first.

If this is homework, please try to solve the problem on your own first, before you ask us to help you. Then, post your code or other work product here for comments, corrections, etc.

In any case, fibonacci numbers are where fib(n) = fib(n-1) + fib(n-2), so exponentiation should not a factor here. Show us the math!

FWIW, I have been using fibonacci sequences for almost 30 years for many situations ranging from balancing stock portfolios to determining the most optimal server to process a network request. Needless to say, it is a subject of which I have some small knowledge... I first implemented the algorithm in C in 1983. :-)

Edited 4 Years Ago by rubberman

#include <stdio.h>
#include <stdlib.h>
void main()
{
    int fib[40],i,n;
    printf("enter the limit of fibonacci series:");
    scanf("%d",&n);
    fib[0]-0;
    fib[1]=1;
    for(i=2;i<n;i++)
    {
        fib[i]=fib[i-1]+fib[i-2];
    }
    for(i=0;i<n;i++)
    {
        printf("\t %d",fib[i]);
    }
}

hii rubber man is it like this??

Let F be the matrix

1 1
1 0

Then F^n (2x2 matrix multiplication) equals

F(n+1) F(n)
F(n)   F(n-1)

because:

(F(n+1) F(n)  ) (1 1) = ( F(n+1)+F(n)   F(n+1))
(F(n)   F(n-1)) (1 0) = ( F(n)+F(n-1)   F(n)  )

So, @rubberman when F matrix is multiplied n times using divide and conquer(which is very casual as we can calculate n^p in logn time) we get F(n). But my problem is that i have done n^p for integers only. I am not getting how can i do this with F matrix given above? I have given the logic above, So please try to help me. thanks in advance.

Edited 4 Years Ago by I_m_rude

This article has been dead for over six months. Start a new discussion instead.