Fib for Fun

February 21st 2009 | Tags: programming

A little math can be a dangerous thing. Here's a quick benchmark for Fibonacci numbers (Y axis in seconds, 20,000 iterations):


The line on the left, marked A, is the typical naive recursive solution, based as directly as possible on the mathematical definition of the function:

def fib_r(n)
  return 1 if n <= 2
  fib_r(n-1) + fib_r(n-2)

Note the telltale exponential curve - this is what we call Very Bad. The line there stops at Fib(10).

A little jiggery lets us convert the recursive solution into an iterative one, line B:

def fib_i(n)
  x = y = 1
  (n-1).times do
    x, y = y, x+y

My personal favorite Fib function is (ab)using a hash's default value function to act as a memoizer. Line C is the fastest of the bunch (constant time of ~0.012s) but does have some extra memory overhead.

def fib_h(n)
  @h ||={ |h,k|
    if k < 2
      h[k] = k
      h[k] = h[k-1] + h[k-2]

If we were in an embedded system or something, the memory overhead would probably be bad, but fear not! Math can save us!

Line D is also constant time, but about 0.037s. It's a fun little bit of math mentioned in SICP, and turns Fibonacci numbers into a very simple (if unintuitive) bit of math:

SQRT5 = Math.sqrt(5.0)
PHI = (1 + SQRT5) / 2
PSI = (1 - SQRT5) / 2

def fib_m(n)
  ((PHI ** n - PSI ** n) / SQRT5).to_i

blog comments powered by Disqus