## Fib for Fun

21st Feb 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:

1
2
3
4

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

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:

1
2
3
4
5
6
7

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

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.

1
2
3
4
5
6
7
8
9
10

def fib_h(n)
@h ||= Hash.new{ |h,k|
if k < 2
h[k] = k
else
h[k] = h[k-1] + h[k-2]
end
}
@h[n]
end

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:

1
2
3
4
5
6
7

SQRT5 = Math.sqrt(5.0)
PHI = (1 + SQRT5) / 2
PSI = (1 - SQRT5) / 2
def fib_m(n)
((PHI ** n - PSI ** n) / SQRT5).to_i
end