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[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)**

## One thought on “Fibonacci Numbers in O(logn) [Matrix Exponentiation]”