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

Brent Yorgey wrote:

On Nov 5, 2007 5:22 PM, gitulyar mailto:gitulyar@gmail.com> 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 really TOO SLOW.

Tell me please if I have something missed, maybe some compiler (interpretaitor) options (I use ghc 6.6.1).

P.S. As I understand function "fib n" should be calculated one time. For example if I call "fib 30" compiler builds tree in which call function "fib 28" 2 times and so on. But as for lazy calculation principle it should be calculated just ones and then it's value is used for all other calls of this function with the same argument. But it seems that this principle doesn't

work in this algorithm.

Lazy evaluation is not the same thing as memoization. This algorithm for calculating fibonacci numbers is just as inefficient in Haskell as it is in any other language. Lazy evaluation has to do with *when* things get executed, not saving the values of function calls to be used in place of other calls with the same arguments.

For a more efficient Haskell implementation of fibonacci numbers, try

fibs :: [Integer] fibs = 1 : 1 : zipWith (+) fibs (tail fibs)

fib n = fibs !! n

-Brent

Close, I believe Brent actually meant

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

In any case, to answer your question more specifically, the memoization of *constants* is essential to the efficient implementation of lazy evaluation, and GHC certainly does it. You can just unroll the loop yourself to see. The following runs as fast as you'd expect: fib00 = 0 fib01 = 1 fib02 = fib00 + fib01 fib03 = fib01 + fib02 fib04 = fib02 + fib03 fib05 = fib03 + fib04 fib06 = fib04 + fib05 fib07 = fib05 + fib06 fib08 = fib06 + fib07 fib09 = fib07 + fib08 fib10 = fib08 + fib09 fib11 = fib09 + fib10 fib12 = fib10 + fib11 fib13 = fib11 + fib12 fib14 = fib12 + fib13 fib15 = fib13 + fib14 fib16 = fib14 + fib15 fib17 = fib15 + fib16 fib18 = fib16 + fib17 fib19 = fib17 + fib18 fib20 = fib18 + fib19 fib21 = fib19 + fib20 fib22 = fib20 + fib21 fib23 = fib21 + fib22 fib24 = fib22 + fib23 fib25 = fib23 + fib24 fib26 = fib24 + fib25 fib27 = fib25 + fib26 fib28 = fib26 + fib27 fib29 = fib27 + fib28 fib30 = fib28 + fib29 main = putStrLn . show $ fib30 The key insight is that by pure syntactic transformation, you can create a graph of fib## that has only (##+1) nodes in it. For a parametrized function fib n, no mere syntactic transformation can be so made. You actually have to evaluate the values (n-1) and (n-2) before you know how to wire the graph, putting it out of reach of a compile-time graph generator.