Here, is code below to calculate nth term of Fibonacci series in log(n) time complexity. Do comment if find any bug. Thanks E-mail :- surajjumpy@gmail.com
#include<iostream>
using namespace std;
void ope(int F[2][2], int M[2][2])
{
int x = F[0][0]*M[0][0] + F[0][1]*M[1][0];
int y = F[0][0]*M[0][1] + F[0][1]*M[1][1];
int z = F[1][0]*M[0][0] + F[1][1]*M[1][0];
int w = F[1][0]*M[0][1] + F[1][1]*M[1][1];
F[0][0] = x;
F[0][1] = y;
F[1][0] = z;
F[1][1] = w;
}
void mul(int M[2][2],int n)
{
if(n <= 1)
return;
int F[2][2]={1,1,1,0};
mul(M,n/2);
ope(M,M);
if(n&1)
ope(M,F);
}
int fab(int n)
{
if(n == 0)
return 0;
int M[2][2] = {1,1,1,0};
mul(M,n-1);
return M[0][0];
}
int main()
{
int i;
cout<<"Enter the term no. ";
cin>>i;
cout<<"\nThe "<<i<<" term is : "<<fab(i);
return 0;
}
No comments:
Post a Comment
Your comment is valuable to us