Project Nayuki


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

Benchmark graph

All algorithms, naïve multiplication

Benchmark graph

All algorithms, Karatsuba multiplication

Benchmark graph

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.

Source code

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}\)