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.
Source code
Java implementation: fastfibonacci.java (all 3 algorithms, timing demo)
Python implementation: fastFibonacci.py (fast doubling only)
Haskell implementation: fastFibonacci.hs (fast doubling only)
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}\)
