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,

{\displaystyle F_{0}=0,\quad F_{1}=1,}

and for n > 1,

{\displaystyle F_{n}=F_{n-1}+F_{n-2}}

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)
....
...

Similarly,

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

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

Leave a Reply