fibonacci series(O(logn))

general
,
1

here is a code for printing fibonacci series O(logn) i found in a book…but i am unable to get the logic…please somebody explain it to me…

long fibonacci(long n)
{
    long i,h,j,k,t;
    i=h=1;
    j=k=0;
    while(n>0) {
        if(n%2==1){
            t=j*h;
            j=i*h + j*k +t;
            i=i*k + t;
        }
        t=h*h;
        h=2*k*h + t;
        k=k*k + t;
        n=(long) n/2;
    }
    return j;
}
2 Likes
2

Read this

I don’t know about your method but this also works in O(logN) and it’s a lot easier to understand\code.

1 Like
3

It is the same…

4

Hi

The program is returning "n"th fibonacci value and not the series .

If u pass 9 program will return you 9th fibonacci value
Example :x9 = x9-1 + x9-2 = x8 + x7 = 21 + 13 = 34

Step1: (9%2 ==1) if(true) j=1 and n=9 h=1 k=0 t=1
Step2: (4%2==0) if(false) n=4 ,t=1,h=3,k=2
Step3: (2%2==0) if(false) n=2 ,t=9, h=21,k=13
Step4: (1%2==1) if(true) n=1 ,t=21,j=34,k=610

j is nth fibonacci value

1 Like
5

following two equation are the basis for the calculating nth fabonacci number
**
f(2n)=f(n)*f(n)+f(n+1)f(n+1)
and
f(2n+1)=2f(n)f(n+1)+f(n+1)f(n+1)

a recursive solution is made by above equations and and converted to iterative and it is all logic here used.

5 Likes