# 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 ...`

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 therest.`

#### 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;}`
One clap, two clap, three clap, forty?

By clapping more or less, you can signal to us which stories really stand out.