Re: [Haskell-cafe] Fibonacci numbers generator in Haskell

I guess I don't get any points for an approximate solution, ay? Is there anything that can be done (easily) to reduce the rounding errors? On 6/15/06 11:23 PM, "ajb@spamcop.net" wrote:

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 _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe