[Haskell-cafe] Fibonacci numbers generator in Haskell
Mathew Mills
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 ]
> [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 at haskell.org
> http://www.haskell.org/mailman/listinfo/haskell-cafe
More information about the Haskell-Cafe
mailing list