# Fibonacci Numbers in O(logn) [Matrix Exponentiation]

In mathematics, the Fibonacci series (F_{n}) is a sequence, such that each number in the series is the sum of the two preceding ones, starting from 0 and 1. That is,

and for n > 1,

In the last post, we discussed O(n) time complexity method to find nth fibonacci number. In this post we’ll learn about O(logn) method using Matrix exponentiation.

###### Matrix Exponentiation

Let’s suppose we have a relation:

F_{n+1} = a*F_{n} + b*F_{n-1}
F_{n} = c*F_{n} + d*F_{n-1}

We could write this relation in form of matrix multiplication like this:

F(N+1)   =   M     *    F(N)
| F_{n+1} |  =  | a b | |F_{n}  |
| F_{n}   |     | c d | |F_{n-1}|

Let’s have a = 1, b = 1, c = 1, and d = 0

Thus we get the following relation:

F_{n+1} = F_{n} + F_{n-1}
F_{n} = F_{n}

which is nothing but the Fibonacci relation. So the required matrix M could be written as M =

              | 1  1 |
| 1  0 |

Now, consider this:

X_{i+1} = M * X_{i}
M * X_{i+1} = M^2 * X_{i} = X_{i+2} (Multiplying both sides by M)
ie. X_{i+2} = M^2 * X_{i} (Replacing i with i+1 in the first equation)
....
...

Similarly,

X_{i+k} = M^k X_{i}

Now, for a special case i = 0, ie.

X_k = M^k X_0
We get,
X_k = M^k I, where I is the identity Matrix or
I = |1  0|
|0  1|

So to find nth Fibonacci number, we just need to calculate:

M^n where M =

              |1  1|
|1  0| 

or,

Matrix multiplication can be done in O(n), by iterating from i=1 to i=n and multiplying matrix M with itself in each iteration ie

M^n = M*M*M*M....

However, we can perform nth exponential in O(logn) using the approach discussed in this article.

Code Implementation

//
//  main.cpp
//  Fibonacci (logn)
//
//  Created by Himanshu on 22/09/21.
//

#include<iostream>
using namespace std;
int res = {{1,0},{0,1}};

void multiply (int F, int M) {
int x = F * M + F * M;
int y = F * M + F * M;
int w = F * M + F * M;
int z = F * M + F * M;

F = x;
F = y;
F = w;
F = z;
}

void power (int F, int n) {

if( n == 0 || n == 1) {
return;
}

while(n>0) {
if(n%2 != 0) {
multiply (res, F);
}

multiply (F, F);
n = n/2;
}
}

int solve(int n) {

int F = {{1, 1}, {1, 0}};

if (n == 1) {
return 0;
} else if (n == 2) {
return 1;
}

power (F, n);

return res;
}

int main() {
int n = 15;

printf("%dth Fibonacci number is %d\n", n, solve(n));

return 0;
}


Output

15th Fibonacci number is 377

Time Complexity: O(logn)
Auxiliary Space: O(1)