Computing Fibonacci Numbers

Boosting Matrix Exponentiation

We're jumping several levels of abstraction: instead of thinking purely about mathematical algorithms, we're going to think about how computers work, and how we can speed up a very specific algorithm using some tricks. In applied math problems, getting the mathematical answer can be only half the battle—getting code to run efficiently on actual hardware is a different challenge. We're going to start with our matrix exponentiation algorithm and really make it sing.

Recall that matrix exponentiation means computing $M^n$, where $M = \begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix}$. Let's just show what the first few powers look like:

$$\begin{aligned} M &= \begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix} \\ M^2 &= \begin{pmatrix} 2 & 1 \\ 1 & 1 \end{pmatrix} \\ M^3 &= \begin{pmatrix} 3 & 2 \\ 2 & 1 \end{pmatrix} \\ M^4 &= \begin{pmatrix} 5 & 3 \\ 3 & 2 \end{pmatrix} \\ \end{aligned}$$

We can spot the general form by this point:¹

$$M^n = \begin{pmatrix} F(n+1) & F(n) \\ F(n) & F(n-1) \end{pmatrix}$$