[Haskell-cafe] Fibonacci numbers generator in Haskell

[ajb at spamcop.net]

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