fibo number

[I_m_rude]

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

thanks in advance.

[np complete]

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

[rubberman]

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. :-)

[rithish]

#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??

[np complete]

Yes, this is the one that rubberman is talking about.

[I_m_rude]

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.