Why We Calculate Fibonacci Numbers ?How to find nth term using Matrix Exponentiation with only O(logn) complexity?

Fibonacci sequence was introduced in our syllabus in 10th or 9th.So we have calculated them but why we need to calculate them ?

So the answer is its importance in our real world.If you start finding its applications you will be surprised .

There are many uses of Fibonacci numbers but let us see some important ones:

Click on the image or Zoom to read it clearly

The link in the reference will provide hundreds of applications.

Now How to Solve:

We traditionally use the formula fib(n)=fib(n-1)+fib(n-2) but using it in our program with recursion will not be feasible with how value n and have complexity of O(n) so we will introduce Matrix Exponentiation to find nth term.

We can find the term using this approach:

Example:

But here as n increases the matrix exponent also increases so to make easy for algorithm to do it we will use fast exponentiation method.

what we will do in fast exponentiation is we will divide out exponent (n-1) with 2 recursively cause when one time matrix is multiplied with itself then if we multiply that answer with itself it will give us the multiplication of out matrix four times .

Here the link from my fellow medium writer if you want to understand fast exponentiation in details:

Fast Exponentiation using Dynamic Programming

Program:

#include<iostream>
using namespace std;
void multiply(unsigned long long F[2][2],unsigned long long M[2][2]);

void power(unsigned long long F[2][2],unsigned long long n);

/* function that returns nth Fibonacci number */
unsigned long long fib(unsigned long long n)
{ unsigned long long F[2][2] = {{1,1},{1,0}};
if (n == 0)
return 0;
power(F, n-1);
return F[0][0];
}

void power(unsigned long long F[2][2],unsigned long long n)
{
if( n == 0 || n == 1)
return;
unsigned long long M[2][2] = {{1,1},{1,0}};

power(F, n/2);
multiply(F, F);

//Marvin Raval

if (n%2 != 0)
multiply(F, M);
}

void multiply(unsigned long long F[2][2],unsigned long long M[2][2])
{
unsigned long long x = F[0][0]*M[0][0] + F[0][1]*M[1][0];
unsigned long long y = F[0][0]*M[0][1] + F[0][1]*M[1][1];
unsigned long long z = F[1][0]*M[0][0] + F[1][1]*M[1][0];
unsigned long long 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;
}

int main()
{
unsigned long long n = 40;
cout<<fib(n)<<endl;

}

Traditional program made with c/c++ will crash or take long time to give answer after N=40 .You can try it on your program. But this program will answer upto 10¹⁵ without much delay it is tested by me.

Complexity:

Now you probably guessing how it reduces the complexity as it uses matrix multiplication with large exponents.But because here we are using 2*2 matrix we can do it in O(1) only in 4 statements directly.So the only affecting N will the exponent of the matrix .

Cause here T(n)=T(n/2)+1 after applying master theorem the answer would be O(logn).

Thats it , If you liked it than clap and follow me.

Thanks for reading :)

References:

Find Nth term (A matrix exponentiation example) - GeeksforGeeks

What are the real life applications of Fibonacci series?