Fri, 27 Feb 2009

I am tired of seeing really inefficient fibonacci sequence functions
all over the place. I fear that someone might, someday, use one in a
setting where it matters, therefore let me set the record straight
with some *proper* fib examples!

Ruby

module Math
PHI = (1 + Math.sqrt(5)) / 2
end
def fib n
(((Math::PHI ** n) - ((1 - Math::PHI) ** n) ) / Math.sqrt(5)).to_i
end

Haskell

let fib n =
let phi = (1 + sqrt 5) / 2 in
round ((phi^n - (1 - phi)^n) / (sqrt 5))

Now I can go to bed :-)