More Efficient Fibonacci?

[xcthulhu]

Nice to see another person doing CS101 to keep themselves sharp. There are a couple of cute O(ln(n)) Fibonacci calculators to try:

• There's a very clever iterative solution in Abelson and Sussman's SICP (Ex. 1.19)
  https://github.com/sarabander/sicp-pdf/raw/master/sicp.pdf
• There's another crazy solution using Matrix exponentiation:
  https://en.wikipedia.org/wiki/Fibonacci_number#Matrix_form
  You'll want an iterative O(ln(n)) matrix exponentiation algorithm, however, so you should check out SICP (Ex. 1.16)
• There's also the old trick of rounding powers of the golden ratio:
  https://en.wikipedia.org/wiki/Fibonacci_number#Computation_by_rounding
  Again, you can do this one iteratively in O(ln(n)), although a hand crafted exponentiation function will never outperform Math.pow on Chrome.
• Another approach is to use Binet's formula: fib(n) = (phi^n - phi^(-n)) / sqrt(5) ; you can use this iteratively without rounding by defining a custom class for Z[sqrt(5)]; see Integral Extensions for a discussion of this idea. Here's an implementation (in Haskell): https://github.com/jaycoskey/RealWorldBenchmarking/blob/master/Fibonacci/extension.hs
• Another neat way to solve this problem is to derive the closed form of the recurrence using the z transform. Here's a MathOverflow about it: https://math.stackexchange.com/questions/279868/causal-inverse-z-transform-of-fibonacci
  Again, an efficient, exact solution would require expressing the zeros of x^2 -x - 1 in Z[sqrt(5)] and defining iterative O(ln(n)) integer exponentiation for that ring. All of the ring extension solutions are less efficient than Abelson and Sussman's solution.

[felipernb]

Thanks! I'll take a look when I get some time. Feel free to send a PR if you feel like :)