Fibonacci Funhouse
summary
Starts with naive recursion that times out after ~32 and a Binet float formula that fails around 70 and throws a float error at ~1,475; switching to bigdecimal at 1,000 precision pushes correctness but slows things and rationals hit trouble near ~6,000. Enabling tail call optimization and disabling tracing lets a tail-recursive approach reach ~100,000. Moving to repeated squaring matrix exponentiation and especially fast doubling with memoized hash default proc blows past millions — the billionth Fibonacci (208,987,... digits) computes in ~10 seconds in Ruby.
AI-written summary · about
chapters (14)
- 0:00Fibonacci Funhouse welcome
- 1:51Helpful interviewer intro
- 2:33Naive Fibonacci flaws
- 4:58Binet's constant time attempt
- 7:48Floating point precision issues
- 9:11BigDecimal for precision
- 11:39Rational numbers approach
- 13:45Tail call optimization in Ruby
- 16:08Iterative Fibonacci with enumerators
- 18:16Matrix multiplication method
- 21:26Repeated squares explained
- 24:19Fast doubling method
- 28:12C extensions vs Ruby performance
- 30:20Final thoughts
