[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