Starred Problem #2 — Nth Fibonacci Number in Log(n) Time

Problem

You have to write a program that generates values from the Fibonacci sequence. The Fibonacci sequence is recursively defined by:

Fn = Fn - 1 + Fn - 2

Using the following seed values:

F0 = 0, F1 = 1

Given a number n, print the nth value of the Fibonacci sequence.

if you are fibonacci fan, you can see following for fun ...

Examples

Input:

12

Output:

144

Input:

30

Output:

832040

Solution

there are 6 to 7 ways of writing solution to this problem and i do not want to go into details of every solution, rather we are going to discuss the most efficient way to find the nth fibonacci number which will be O(log n) time.
Nth Fibonacci  can be represented in following a matrix identity form:

We will be using an Intelligent Strategy to get the nth power of Matrix in log(n) time. This strategy is formally called Dynamic Programming.
Here can represent

in the form of a tree:

Now, what if Power of M is odd, then we have to calculate for 1 less than it and then multiply M to the product we get from the
rest.

C++ Code

#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;

void multiply(int mat[2][2],int m[2][2]){
   int temp[2][2];
   temp[0][0]=mat[0][0]*m[0][0]+mat[0][1]*m[1][0];
   temp[0][1]= mat[0][0]*m[0][1]+mat[0][1]*m[1][1];
   temp[1][0]= mat[1][0]*m[0][0]+mat[1][1]*m[1][0];
   temp[1][1]= mat[1][0]*m[0][1]+mat[1][1]*m[1][1];
   mat[0][0]=temp[0][0];
   mat[0][1]=temp[0][1];
   mat[1][0]=temp[1][0];
   mat[1][1]=temp[1][1];
}

void mat_power(int mat[2][2],int n){
   if(n==1) return; // n==0 will never come
  
    mat_power(mat,n/2);
    multiply(mat,mat);
  
    int m[2][2]={
       {1,1},
       {1,0}
       };   
    if(n%2!=0)
	    multiply(mat,m);
}


int main() {
   int n;
   cin>>n;
   
   int mat[2][2]={
       {1,1},
       {1,0}
       };   
    if(n==0) cout<< 0<<endl;
    mat_power(mat,n);
    cout<<mat[0][1]<<endl;
    return 0;
}