# Fast Fibonacci algorithms

Definition: The Fibonacci sequence is defined as $$F(0) = 0$$, $$F(1) = 1$$, and $$F(n) = F(n-1) + F(n-2)$$ for $$n \ge 2$$. So the sequence (starting with $$F(0)$$) is $$0, 1, 1, 2, 3, 5, 8, \ldots$$.

If we wanted to compute a single term in the sequence (e.g. $$F(n)$$), there are a couple of algorithms to do so, but some algorithms are much faster than others.

## Algorithms

Recursive algorithm (extremely slow)

Naïvely, we can directly execute the recurrence as given in the mathematical definition of the Fibonacci sequence. Unfortunately, it’s hopelessly slow: It uses $$O(n)$$ stack space and $$O(\phi^n)$$ time, where $$\phi = \frac{\sqrt{5} + 1}{2}$$ (the golden ratio). In other words, the amount of time to compute $$F(n)$$ is proportional to the resulting value itself, which grows exponentially.

Dynamic programming (slow)

It should be clear that if we’ve already computed $$F(k-2)$$ and $$F(k-1)$$, then we can add them to get $$F(k)$$. Next, we add $$F(k-1)$$ and $$F(k)$$ to get $$F(k+1)$$. We repeat until we reach $$k = n$$. Most people notice this algorithm automatically, especially when computing Fibonacci by hand.

Matrix exponentiation (medium)

The algorithm is based on this innocent-looking identity (which can be proven by mathematical induction):

$$\left[ \begin{matrix} 1 && 1 \\ 1 && 0 \end{matrix} \right]^n = \left[ \begin{matrix} F(n+1) && F(n) \\ F(n) && F(n-1) \end{matrix} \right]$$.

It is important to use exponentiation by squaring with this algorithm, because otherwise it degenerates into the dynamic programming algorithm.

Fast doubling (fast)

Given $$F(k)$$ and $$F(k+1)$$, we can calculate these:

\begin{align} F(2k) &= F(k) \left[ 2F(k+1) - F(k) \right]. \\ F(2k+1) &= F(k+1)^2 + F(k)^2. \end{align}

These identities can be extracted from the matrix exponentiation algorithm. In a sense, this algorithm is the matrix exponentiation algorithm with the redundant calculations removed.

Summary: The two fast Fibonacci algorithms are matrix exponentiation and fast doubling. They have the same asymptotic time complexity, but fast doubling is faster than matrix exponentiation by a significant constant factor. Both algorithms use multiplication, so they become even faster when Karatsuba multiplication is used. The other two algorithms are slow. They don’t use multiplication; they only use addition.

## Benchmarks

All algorithms, naïve multiplication

All algorithms, Karatsuba multiplication

Fast algorithms, both multiplication algorithms

The tests were performed on Intel Core 2 Quad Q6600 (2.40 GHz) using a single thread, Windows XP SP 3, Java 1.6.0_22.

## Proofs

Matrix exponentiation

We will use weak induction to prove this.

Base case

For $$n = 1$$, clearly $$\left[ \begin{matrix} 1 && 1 \\ 1 && 0 \end{matrix} \right]^1 = \left[ \begin{matrix} F(2) && F(1) \\ F(1) && F(0) \end{matrix} \right]$$.

Induction step

Assume $$\left[ \begin{matrix} 1 && 1 \\ 1 && 0 \end{matrix} \right]^n = \left[ \begin{matrix} F(n+1) && F(n) \\ F(n) && F(n-1) \end{matrix} \right]$$. Then:

$$\left[ \begin{matrix} 1 && 1 \\ 1 && 0 \end{matrix} \right]^{n+1} \\ = \left[ \begin{matrix} 1 && 1 \\ 1 && 0 \end{matrix} \right]^n \left[ \begin{matrix} 1 && 1 \\ 1 && 0 \end{matrix} \right] \\ = \left[ \begin{matrix} F(n+1) && F(n) \\ F(n) && F(n-1) \end{matrix} \right] \left[ \begin{matrix} 1 && 1 \\ 1 && 0 \end{matrix} \right] \\ = \left[ \begin{matrix} F(n+1)+F(n) && F(n+1)+0 \\ F(n)+F(n-1) && F(n)+0 \end{matrix} \right] \\ = \left[ \begin{matrix} F(n+2) && F(n+1) \\ F(n+1) && F(n) \end{matrix} \right].$$

Fast doubling

We will assume the fact that the matrix exponentiation method is correct.

$$\left[ \begin{matrix} F(2n+1) && F(2n) \\ F(2n) && F(2n-1) \end{matrix} \right] \\ = \left[ \begin{matrix} 1 && 1 \\ 1 && 0 \end{matrix} \right]^{2n} \\ = \left( \left[ \begin{matrix} 1 && 1 \\ 1 && 0 \end{matrix} \right]^n \right)^2 \\ = \left[ \begin{matrix} F(n+1) && F(n) \\ F(n) && F(n-1) \end{matrix} \right]^2 \\ = \left[ \begin{matrix} F(n+1)^2+F(n)^2 && F(n+1)F(n)+F(n)F(n-1) \\ F(n)F(n+1)+F(n-1)F(n) && F(n)^2+F(n-1)^2 \end{matrix} \right].$$

Therefore, by equating the cells in the matrix:

\begin{align} F(2n+1) &= F(n+1)^2 + F(n)^2. \\ F(2n) &= F(n) \left[ F(n+1) + F(n-1) \right] \\ &= F(n) \left[ F(n+1) + (F(n+1) - F(n)) \right] \\ &= F(n) \left[ 2F(n+1) - F(n) \right]. \\ F(2n-1) &= F(n)^2 + F(n-1)^2. \end{align}