[Haskell-cafe] Fibbonachi numbers algorithm work TOO slow.
Dan Weston
westondan at imageworks.com
Mon Nov 5 18:18:31 EST 2007
Brent Yorgey wrote:
>
> On Nov 5, 2007 5:22 PM, gitulyar <gitulyar at gmail.com
> <mailto:gitulyar at 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.
More information about the Haskell-Cafe
mailing list