[Haskell-cafe] Fibonacci numbers generator in Haskell
mathewmills at mac.com
Fri Jun 16 08:54:57 EDT 2006
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 at spamcop.net" <ajb at spamcop.net> wrote:
> 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 ]
> 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.
> Andrew Bromage
> Haskell-Cafe mailing list
> Haskell-Cafe at haskell.org
More information about the Haskell-Cafe