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.
- Recursive algorithm (extremely slow)
Naïvely, we can directly execute the recurrence as given in the 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 without much effort.
- Matrix exponentiation (medium)
-
The algorithm is based on this innocent-looking identity:
\( \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] \)
(Note: The identity can be proven by mathematical induction.)
It is important to use exponentiation by squaring with this algorithm, 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.
Code
Java implementation: fastfibonacci.java (all 3 algorithms, timing demo)
Python implementation: fastFibonacci.py (fast doubling only)
Haskell implementation: fastFibonacci.hs (fast doubling only)
