## Fast Recurrences

Quite a while ago, I wrote a post on how to compute an arbitrarily large Fibonacci number $F_n$ in essentially $O(\log n)$ steps. Turns out, that technique generalizes to other recurrence relations, and of any order.

Let’s recall (and change the notation somewhat), that for the Fibonacci numbers,

$\left[~ \begin{matrix} 1 & 1 \\ 1 & 0 \end{matrix} ~\right]^{n-1} \left[~ \begin{matrix} 1\\ 1 \end{matrix} ~\right] = \left[~ F_{n+1}\\ F_n ~\right]$.

With the special case were the matrix to the zeroth power is the identity matrix. We know this will work as intended, because

$\left[~ \begin{matrix} F_{n+1}\\ F_n \end{matrix} ~\right] = \left[~ \begin{matrix} 1 & 1 \\ 1 & 0 \end{matrix} ~\right] \left[~ \begin{matrix} F_{n}\\ F_{n-1} \end{matrix} ~\right] = \left[~ \begin{matrix} F_{n}+F_{n-1}\\ F_{n} \end{matrix} ~\right] = \left[~ \begin{matrix} F_{n+1}\\ F_{n} \end{matrix} ~\right]$.

This is basically a recursive definition of the matrix exponentiation.

This clever strategy is efficient because we can compute the power of the matrix in $O(\log n)$ matrix products—which, in this particular case, are each rather inexpensive.

*
* *

What if we’re interested in some arbitrary recurrence relation, say,

$r_n=r_{n-1}+2r_{n-2}-3r_{n-3}$,

with initial conditions $r_1=1$, $r_2=2$, $r_3=4$? We now discover something the previous example hid well:

$\left[~ \begin{matrix} 1 & 2 &3 \\ 1 & 0 & 0 \\ 0 & 1 & 0 \end{matrix} ~\right]^{n-1} \left[~ \begin{matrix} 4\\ 2\\ 1 \end{matrix} ~\right] = \left[~ \begin{matrix} r_n\\ r_{n-1}\\ r_{n-2} \end{matrix} ~\right]$.

The first row of the matrix is the coefficients of the recurrence relation, the column-vector contain the initial conditions ($r_1$, $r_2$, and $r_3$). You can check that both methods—simple recurrence and matrix version—yield the sequence

1, 2, 4, 5, 7, 5, 4, -7, -14, -40, -47, -85, …

*
* *

The general method for a recurrence relation of order $k$,

$r_n = a_0 r_{n-1} + a_1 r_{n-2} + \cdots + a_{k-1}r_{k-1}$

with $k$ initial conditions $r_0$, $r_1$, … $r_{k-1}$, we have

$\left[~ \begin{matrix} a_0 & a_1 & a_2 & \cdots & a_{k-2} & a_{k-1}\\ 1 & 0 & 0 & \cdots & 0 & 0 \\ 0 & 1 & 0 & \cdots & 0 & 0 \\ \vdots & \vdots & \vdots & \cdots & \vdots & \vdots\\ 0 & 0 & 0 & \cdots & 1 & 0 \end{matrix} ~\right]^{n-k+1} \left[~ \begin{matrix} r_{k-1}\\ r_{k-2}\\ \vdots\\ \vdots\\ r_{0} \end{matrix} ~\right] = \left[~ \begin{matrix} r_n\\ r_{n-1}\\ \vdots\\ \vdots\\ r_{n-k+1} \end{matrix} ~\right]$.

Clearly, the first line of the matrix is composed of the $a_i$, the coefficients of the recurrence relation, but what are the other lines’ function? They act as a shift mecanism, so that we move down the $k-1$ previously computed values one position down in the sequence, making some place for the new value given by the dot product with the first line. That is, it computes:

$(r_{n-1},r_{n-2},r_{n-3}\ldots,r_{n-k}) \to (r_{n},r_{n-1},r_{n-2}\ldots,r_{n-k+1})$,

with

$\displaystyle r_n = \sum_{i=0}^{k-1} a_i r_{n-i-1}$.

*
* *

So, now, we can compute any recurrence relation for arbitrarily large $n$ in $O(\log n)$ matrix multiplications. The matrix multiplications do get more expensive as $k$ grows. If we do it simply, as we were taught in school, multiplying two $k\times{k}$ matrices costs $O(k^3)$, or, if we use Strassen’s algorithm, we can do it in $O(k^{\lg 7})$ (or about $O(k^{2.8})$). That brings the complexity to $O(k^3 \log n)$, which is rapidly smaller than $n$.