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