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

G'day all. I wrote: However, this is still an O(log n) algorithm, because that's the complexity of raising-to-the-power-of. And it's slower than the simpler integer-only algorithms. Quoting Henning Thielemann <[EMAIL PROTECTED]>: You mean computing the matrix power of /1 1\ \0 1/ ? I m

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

Hi, sorry my english is not the best :( 2007/11/5, gitulyar <[EMAIL PROTECTED]>: > > Please help me. I'm new in Haskell programming, but wrote some things in > Scheme. I make so function: > > fib 1 = 1 > fib 2 = 2 > fib n = fib (n-1) + fib (n-2) > > And when I call "fib 30" it works about 5 second

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

There are some nice formulae for the Fibonacci numbers that relate f_m to values f_n where n is around m/2. This leads to a tolerably fast recursive algorithm. Here's a complete implementation: fib 0 = 0 fib 1 = 1 fib 2 = 1 fib m | even m = let n = m `div` 2 in fib n*(fib (n-1)+fib (n+1))

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

When discussing the complexity of fib don't forget that integer operations for bignums are no longer constant time. -- Lennart On Nov 7, 2007 6:55 AM, Henning Thielemann <[EMAIL PROTECTED]> wrote: > > On Tue, 6 Nov 2007 [EMAIL PROTECTED] wrote: > > > However, this is still an O(log n) algorithm

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

On Tue, 6 Nov 2007 [EMAIL PROTECTED] wrote: > However, this is still an O(log n) algorithm, because that's the > complexity of raising-to-the-power-of. And it's slower than the > simpler integer-only algorithms. You mean computing the matrix power of /1 1\ \0 1/ ?

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

G'day all. Quoting [EMAIL PROTECTED]: 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 no

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

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 [EMAIL PROTECTED] wrote: Andrew Bromage: G'day all. (MIS)Quoting Dan

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

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/g

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

G'day all. Quoting Dan Weston <[EMAIL PROTECTED]>: In any case, to answer your question more specifically, the memoization of *constants* I think you meant "CAFs". You can just unroll the loop yourself to see. The following runs as fast as you'd expect: fib00 = 0 fib01 = 1 fib02 = fib00 +

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

Brent Yorgey wrote: On Nov 5, 2007 5:22 PM, gitulyar <[EMAIL PROTECTED] > wrote: Please help me. I'm new in Haskell programming, but wrote some things in Scheme. I make so function: fib 1 = 1 fib 2 = 2 fib n = fib (n-1) + fib (n-2) And when

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

> For a more efficient Haskell implementation of fibonacci numbers, try > > fibs :: [Integer] > fibs = 1 : 1 : zipWith (+) fibs (tail fibs) > > fib n = fibs !! n This is uglier, but just to keep using just plain recursion: fib = fib' 0 1 where fib' a b 0 = a fib' a b n = fib' b (a+b) (n

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

On Nov 5, 2007 5:22 PM, gitulyar <[EMAIL PROTECTED]> wrote: > > Please help me. I'm new in Haskell programming, but wrote some things in > Scheme. I make so function: > > fib 1 = 1 > fib 2 = 2 > fib n = fib (n-1) + fib (n-2) > > And when I call "fib 30" it works about 5 seconds. As for me it's rea

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

Please help me. I'm new in Haskell programming, but wrote some things in Scheme. I make so function: fib 1 = 1 fib 2 = 2 fib n = fib (n-1) + fib (n-2) And when I call "fib 30" it works about 5 seconds. As for me it's really TOO SLOW. Tell me please if I have something missed, maybe some compile