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

Guido Genzone guidog87 at gmail.com
Wed Nov 7 22:11:53 EST 2007


Hi,

sorry my english is not the best :(
2007/11/5, gitulyar <gitulyar at gmail.com>:
>
> 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.

Because the scheme is Inefficient
If you define fib like this:

dfib 0 = (1,1)
dfib n = let (a,b) = dfib (n-1) in (b, b+a)
-- dfib n = (fib n, fib (n+1)) this explote lazy evaluation

fib n = fst (dfib n)

With this definition the lazy evaluation calculate only one fib 1, one
fib 2......etc.


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

The scheme is bad, no ghci.

> 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.

If you have this:
mult:Int->Int
mult x = x + x + x
-------------------------------------------------------------------
mult (fib 20)

=      <Definition>
(fib 20)  + (fib 20)  + (fib 20)

=        < By lazy evaluation, this is equal..>
x + x + x
    where x = fib 20
-------------------------------------------------------------------
In this case fib 20 calculate only the first call, no three times.

But fib 20

fib 20
=  < Definition>
fib 19 + fib 18

Then the calulate of fib 19 and fib 18 individualy


More information about the Haskell-Cafe mailing list