16 Jun
2006
16 Jun
'06
2:23 a.m.
G'day all.
Quoting Mathew Mills
How about the closed form ;)
-- fib x returns the x'th number in the fib sequence
fib :: Integer -> Integer
fib x = let phi = ( 1 + sqrt 5 ) / 2
in truncate( ( 1 / sqrt 5 ) * ( phi ^ x - phi' ^ x ) )
Seems pretty quick to me, even with sqrt and arbitrarily large numbers.
I called my version "fib" and your version "fib2". I get: *Fib> [ i | i <- [30..100], fib i == fib2 i ] [32,35,43,46,51,71] Yes, the closed form is faster. But if, as part of the rules, one is allowed to give wrong answers, it's not difficult to write a function that's even faster than this. Cheers, Andrew Bromage