Using matrix multiplication to calculate Fibonacci numbers

In this post, we will discuss how to calculate the $n^{th}$ Fibonacci number using matrix multiplication. To skip straight to the code, click here.

Matrix Multiplication

This algorithm involves multiplying 2x2 matrices together, more specifically this matrix…

\begin{bmatrix}1 & 1 \\ 1 & 0\end{bmatrix}

For a reminder on how to multiply matrices, view this article on mathsisfun.

Using the matrix

The matrix above can be used to calculate the $n^{th}$ Fibonacci number. By raising the matrix to the power of $n-1$ , we can get the $n^{th}$ Fibonacci number.

The result of the matrix multiplication will be a matrix with the $n^{th}$ fibonacci number in the top left corner.

Example

To find the $6^{th}$ number in the sequence, we raise the matrix to the power 5…

\begin{bmatrix}1 & 1 \\ 1 & 0\end{bmatrix}^5 = \begin{bmatrix}\textbf{8} & 5 \\ 5 & 3\end{bmatrix}

and we look at the number in the top left corner of the resulting matrix.

Therefore, the $6^{th}$ number in the sequence is 8

Speeding up with fast exponents

We can use a simple maths trick to speed up raising our matrix to large powers. Consider the following examples…

2^4 \equiv ({2^2})^2

2^5 \equiv 2 * ({2^2})^2

From this we see that $2^4$ can be calculated by squaring $2^2$ and $2^5$ can be calculated by simply multiplying $2^4$ by 2.

Although this seems trivial, it can be used to calculate $A^n$ very quickly by simply breaking down the power into smaller powers.

We can generalise this formula …

A^n = \begin{cases} (A^{\frac{n}{2}})^2 & \text{if } n \text{ is even} \\ A \cdot A^{n-1} & \text{if } n \text{ is odd} \end{cases}

Example

To get the $12^{th}$ number in the sequence…

\begin{bmatrix}1 & 1 \\ 1 & 0\end{bmatrix}^{12} \equiv \left({\begin{bmatrix}1 & 1 \\ 1 & 0\end{bmatrix}^6}\right)^2

\begin{bmatrix}1 & 1 \\ 1 & 0\end{bmatrix}^{6} \equiv \left({\begin{bmatrix}1 & 1 \\ 1 & 0\end{bmatrix}^3}\right)^2

\begin{bmatrix}1 & 1 \\ 1 & 0\end{bmatrix}^{3} \equiv \begin{bmatrix}1 & 1 \\ 1 & 0\end{bmatrix} * \left({\begin{bmatrix}1 & 1 \\ 1 & 0\end{bmatrix}^2}\right)^2

As we can see, we can calculate the $12^{th}$ number in the sequence by breaking it down into smaller powers and multiplying them together. This problem is well suited to recursion, as $n$ gets larger, the number of computations increases at a rate of $O(\log{n})$

Code

import numpy as np


def matrix_power(M, n):
    """
    When we want to raise a matrix M to the power of n
    we can use simply matrix multiplication, i.e multiply the matrix n times
    """

    # If n is simply 1, then just return the matrix
    if n == 1:
        return M

    # If n is even
    elif n % 2 == 0:

        # Call recursively with the product of multiplying the matrix by itself, but half the exponent each time
        return matrix_power(np.dot(M, M), n // 2)

    # If n is odd
    else:
        # We simply multiply m by the recursive call from the previous value of n
        return np.dot(M, matrix_power(np.dot(M, M), (n - 1) // 2))


def fib_solution_5(n):
    """
    This solution will use matrix multiplication to find the nth
    fibonacci number

    To find the nth fib number using matrix multiplication, we can multiply the following matrix by n-1...

    ------
    1   1
    1   0
    ------

    The index [0,0] of this matrix will be the value of the nth fibonacci number

    """

    if n <= 1:
        return n

    # Create our matrix to begin multiplication
    m = np.array([[1, 1], [1, 0]])

    # Raise our matrix to the power n and use our optimised function to do it efficiently
    # Then simply extract the answer from the matrix in cell [
    return matrix_power(m, n - 1)[0, 0]