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

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)