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

In mathematics, the Fibonacci series (Fn) 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 = aF_n + bF_n-1

F_n = cF_n + dF_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)
....
...

Similarly,

M^k X_i = X_i+k

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

M^k X_0 = X_k
We get,M^k I = X_k, 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 could perform nth exponential in O(logn) using the approach discussed in this article.

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

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

void multiply (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 w = F[1][0] * M[0][0] + F[1][1] * M[1][0];
int z = F[1][0] * M[0][1] + F[1][1] * M[1][1];

F[0][0] = x;
F[0][1] = y;
F[1][0] = w;
F[1][1] = z;
}

void power (int F[2][2], 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[2][2] = {{1, 1}, {1, 0}};

if (n == 1) {
return 0;
} else if (n == 2) {
return 1;
}
power (F, n);
return res[1][1];
}

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)