Fibonacci Funhouse
summary
Starts with the exponential recursive method (gets useless near n≈30) then implements Binet with BigDecimal (works to ~350 before float/precision slows it), switches to rationals (correct to ~5,994), enables tail-call optimization to reach hundreds of thousands, uses matrix exponentiation by squaring to hit millions, and finally implements fast‑doubling plus memoization (Hash default_proc) to compute the billionth Fibonacci in ~10s producing ~28 million digits — claims Ruby matches C on that machine.
AI-written summary · about
chapters (16)
- 0:00Introduction to Fibonacci Funhouse
- 2:53What are Fibonacci numbers
- 4:15Basic recursive algorithm
- 5:37Performance issues with recursion
- 5:57Binet's formula and constants
- 7:21Problems with Binet's formula
- 8:46BigDecimal for precision
- 10:30Rational numbers approach
- 13:42Iterative recursive method
- 15:29Tail call optimization
- 18:22Matrix multiplication method
- 21:35Repeated squares algorithm
- 24:45Bitwise operations in Ruby
- 25:49Fast doubling algorithm
- 28:39Dynamic programming with hashes
- 29:43Conclusion and Q&A
