Chapter 2 · Analysis Framework
Fibonacci four ways
The same numbers, 0, 1, 1, 2, 3, 5, 8, …, computed by four algorithms whose costs differ wildly: exponential, linear, logarithmic, and "constant, until floating point betrays you".
0 – 9 (the tree doubles with every step)
Cost at a glance
| Method | Basic operation | Count for F(n) | n = 30 | Extra memory |
|---|---|---|---|---|
| Recursive definition | addition | F(n+1) − 1 ∈ Θ(φⁿ) | 1,346,268 | Θ(n) stack |
| Bottom-up table | addition | n − 1 | 29 | Θ(n) (or Θ(1) with two variables) |
| Matrix power | 2×2 matrix product | ≤ 2⌊log₂ n⌋ | 7 | Θ(1) matrices |
| Fast doubling | multiplication | 3 per bit of n | 15 | Θ(1) |
| Binet + rounding | one power | "constant" | 1 | Θ(1), but wrong for n ≥ 71 in double precision |
A caveat the counts hide: F(n) has about 0.209·n decimal digits, so for large n even one addition or multiplication is not a constant-time step (Levitin §2.5).
How to read this
- Call tree: each circle is one call F(k), labeled k. Blue: running right now (on the call stack). Green: returned, with its value under it. Purple: a repeat, a call on an argument that was already fully computed somewhere else in the tree. Every purple node is wasted work.
- Table: yellow cells are the two values being added; the red cell is being written. In the two-variable version the grayed cells have been forgotten: only a window of two values is ever kept.
- Matrix power: the bits of n are read from the left. "Square" doubles the exponent of P = Qᵉ; a 1 bit then multiplies by Q to add one. Qᵉ always contains F(e+1), F(e), F(e−1).
- Binet: the plot's vertical axis is logarithmic. The green line is the true gap between φⁿ/√5 and F(n), which shrinks towards 0. The red dots are the gap the computer actually sees; once they reach the dashed line at 0.5, rounding gives a wrong answer.
Try this
- Call tree for n = 5: count the F(1) leaves (5 = F(5)) and the F(0) leaves (3 = F(4)). That is Levitin Exercise 2.5.7 (Problem Set 1, Problem 10): C(n) = F(n), Z(n) = F(n − 1).
- Predict the total number of calls for n = 7 before playing. (2F(8) − 1 = 41.)
- Switch to the table with n = 7: only 6 additions. Then pick "keep only two variables" and watch the window slide.
- Matrix power for n = 13 (binary 1101): predict how many matrix products. (3 squarings + 2 extra multiplies = 5.)
- Binet: load n = 80 and find the first n where rounding fails (n = 71). Why there? A double stores φ with a relative error of about 10⁻¹⁶; raising it to the nth power multiplies that relative error by roughly n, and F(71) ≈ 3 × 10¹⁴, so the absolute error climbs past 0.5.