re: Compute Smart, Not Hard VIEW POST


You make a very good point about brute-forcing vs solving mathematically. Studying fibonacci is a gateway to learning about recurrence relations, beauty of the golden ratio (phi), interesting relation between Fibonacci and Lukas numbers and how phi keeps cropping up in unexpected places :P

IMO, the main issue with using the direct formula is that there are possibilities of errors creeping at multiple stages due to floating point imprecision.

The matrix solution is beautiful. It is computing the formula mentioned behind the scenes. The only issue with that is again the limited range of machine integers. If we can do it with unlimited precision integers it is a very straight-forward way of solving a recurrence relation efficiently.


Sane modern languages do all support infinite integers.

ErlangVM is not optimized for math by any mean, but TCO does it in circa 10 secs (half of which is the length calculation, I guess) on my desktop:

defmodule Fib do
  def fib(curr \\ 1, acc \\ 0, n)
  def fib(_, acc, n) when n <= 0, do: acc
  def fib(curr, acc, n), do: fib(acc, curr + acc, n - 1)

1_000_000 |> Fib.fib() |> to_string() |> String.length()
#⇒ 208988

For greater numbers, it definitely would be exponentially dying.


Yes. Python integers have unlimited precision out of the box. Java has BigInteger in standard library. Not sure about javascript.

Neither Python nor Java has TCO, so these languages are out of the race here.

code of conduct - report abuse