This post originated from an RSS feed registered with Java Buzz by Brian McCallister. Original Post: Proper Fib Feed Title: Waste of Time Feed URL: http://kasparov.skife.org/blog/index.rss Feed Description: A simple waste of time and weblog experiment Latest Java Buzz Posts Latest Java Buzz Posts by Brian McCallister Latest Posts From Waste of Time

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
        floor (((phi^n) - ((1-phi)^n)) / (sqrt 5))

Now I can go to bed :-)