[Haskell-cafe] Fibonacci numbers generator in Haskell

[Doug Quale]

Mathew Mills <mathewmills at mac.com> writes:

> -- fib x returns the x'th number in the fib sequence
> fib :: Integer -> Integer
> fib x = let phi = ( 1 + sqrt 5 ) / 2
>             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.

You don't actually need the part with phi'^x.  Since |phi'| < 1,
phi'^x gets small fast as x increases.  In fact |phi'^x| is always
smaller than 1/2, so -phi'^x in the expression above can be replaced
by +0.5.

Unfortunately with arbitrarily large numbers it gets the answer wrong.
"Arbitrarily large" in this case is smaller than 100.

> fib 100
354224848179261800448

The correct answer is
354224848179261915075

The relative error is very small, so it is a good approximation.