[Haskell-cafe] Fibonacci numbers generator in Haskell
ajb at spamcop.net
ajb at spamcop.net
Fri Jun 16 02:23:38 EDT 2006
G'day all.
Quoting Mathew Mills <mathewmills at mac.com>:
> 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
More information about the Haskell-Cafe
mailing list