Recursion with matrix multiplication

Tivadar Danka small portrait Tivadar Danka
Fibonacci numbers as powers of a matrix

Understanding math will make you a better engineer.

So, I am writing the best and most comprehensive book about it.

There is a mind-blowing application of matrix multiplication: doing recursion (almost) at the speed of light!

By the end of this post, you'll learn precisely how. Trust me, if you are into programming and math, you want to know this trick.

Let's start with the simplest example for recursion: Fibonacci numbers. Each Fibonacci number is the sum of the previous one and the one before. The recursion starts with 0\textstyle 0 and 1\textstyle 1.

F0=1F1=1Fn=Fn1+Fn2\begin{align*} F_0 &= 1 \\ F_1 &= 1 \\ F_n &= F_{n-1} + F_{n-2} \end{align*}

In Python, the implementation is rather straightforward.

2022-03-matrices-and-recursions-01-fibonacci-vanilla.png

Can you guess the issue? The execution is extremely slow, as each function call involves two more calls. Thus, the fibonacci(n) calls itself many times!

If we measure the execution, we find that the time increases exponentially with n.

2022-03-matrices-and-recursions-02-fibonacci-vanilla-timed.png

Is there any way to improve this? Yes. Spoiler alert: it's all about matrix multiplication.

Matrix multiplication from another perspective

Now, let's talk about matrix multiplication. What do you get when multiplying a row and a column vector? Their inner product.

[ab][xy]=ax+by\begin{bmatrix} a & b \end{bmatrix} \begin{bmatrix} x \\ y \end{bmatrix} = ax + by

How does this relate to the Fibonacci numbers? Simple: we can express the Fibonacci recursion in terms of vectors.

[FnFn1][11]=Fn+Fn1=Fn+1\begin{bmatrix} F_n & F_{n-1} \end{bmatrix} \begin{bmatrix} 1 \\ 1 \end{bmatrix} = F_n + F_{n-1} = F_{n + 1}

With one small trick, we can turn this into an iterative process. By adding a second column to the right side, we can copy the n\textstyle n-th Fibonacci number over. Thus, we have a recursive relation:

[FnFn1][1110]=[Fn+Fn1Fn]=[Fn+1Fn].\begin{align*} \begin{bmatrix} F_n & F_{n-1} \end{bmatrix} \begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix} &= \begin{bmatrix} F_n + F_{n-1} & F_n \end{bmatrix} \\ &= \begin{bmatrix} F_{n+1} & F_{n} \end{bmatrix}. \end{align*}

We can express the above without recursion! Applying our matrix recursion n times, we obtain an explicit formula to calculate the Fibonacci numbers:

[FnFn1][1110]n=[Fn+1Fn].\begin{bmatrix} F_n & F_{n-1} \end{bmatrix} \begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix}^n = \begin{bmatrix} F_{n+1} & F_n \end{bmatrix}.

This is much faster to compute.

Just one more step!

By noticing that the Fibonacci numbers start with 0,1,10, 1, 1, we can stack two shifted vectors on top of itself and obtain the n+1n+1-th, n\textstyle n-th, n1n-1-th Fibonacci numbers purely by raising the right matrix to the n\textstyle n-th power:

[F2F1F1F0][1110]n1=[1110]n=[Fn+1FnFnFn1].\begin{align*} \begin{bmatrix} F_2 & F_1 \\ F_1 & F_0 \end{bmatrix} \begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix}^{n-1} &= \begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix}^n \\ &= \begin{bmatrix} F_{n+1} & F_n \\ F_n & F_{n-1} \end{bmatrix}. \end{align*}

By clearing everything up, we obtain an extremely elegant formula:

[1110]n=[Fn+1FnFnFn1]. \begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix}^n = \begin{bmatrix} F_{n+1} & F_n \\ F_n & F_{n-1} \end{bmatrix}.

Tell me it's not beautiful. I dare you.

We can quickly implement the formula in NumPy.

Implementing Fibonacci numbers as matrix powers

Let's see how it performs!

Measuring the execution of Fibonacci numbers when calculated with matrix powers

As you can see, it is much faster than the vanilla version. Moreover, while the vanilla implementation has exponential time complexity, this has linear. Quite the difference!

A small caveat, though. Due to integer overflow, NumPy is not suitable for this task.

Homework for you: write a plain Python implementation that takes advantage of the arbitrarily large ints!

Having a deep understanding of math will make you a better engineer.

I want to help you with this, so I am writing a comprehensive book that takes you from high school math to the advanced stuff.
Join me on this journey and let's do this together!