# [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:
>
>
>     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)

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.

```