[Haskell-cafe] Fibbonachi numbers algorithm work TOO slow.

Dan Weston westondan at imageworks.com
Mon Nov 5 20:04:30 EST 2007


I assume you meant

 > fib n=(((1+s)/2)^n-((1-s)/2)^n)/s where s=sqrt 5

Your solution starts to diverge from reality at n = 76:

 > fibs = 0 : 1 : zipWith (+) fibs (tail fibs)

Prelude> let n = 76 in fibs !! n - round (fib n)
1

jerzy.karczmarczuk at info.unicaen.fr wrote:
> Andrew Bromage:
>> G'day all.
>> (MIS)Quoting Dan Weston:
> 
>>> fib00 = 0
>>> fib01 = 1
>>> fib02 = fib00 + fib01
>> [deletia]
>>> fib7698760 = fib7698759 + fib7698758
>>
>> This is why we don't pay programmers by LOC.
> ...
>> Incidentally, we've been here before.  Check out this thread:
>>     http://comments.gmane.org/gmane.comp.lang.haskell.cafe/19623
> 
> There is one solution missing there (unless I skipped it)
> fib n=((1+s)/2)^n-((1-s)/2)^n)/s where s=sqrt 5
> If some of you complain that this is real, not integer, please remember 
> that
> Leonardo of Pisa thought of applying this to rabbits. Well, rabbits are
> not integers, they eat carrots and have long ears. They are real thing.
> Hm.
> Well, sqrt is Floating.
> Now, floating rabbits are less common.
> Jerzy Karczmarczuk
> 
> _______________________________________________
> 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