[Haskell-cafe] Fibonacci numbers generator in Haskell
Doug Quale
quale1 at charter.net
Thu Jun 15 23:51:50 EDT 2006
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.
More information about the Haskell-Cafe
mailing list