[Haskell-cafe] Fibonacci numbers generator in Haskell

[Mathew Mills]

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