Strict<->Lazy?

[Pieter Koopman]

At 09:10 01/07/99 +0200, Siegfried Gonzi wrote:
>Yesterday I wrote a little program for calculating the fibonacci
>numbers. I do know from Maple that, e.g. evaluating the fibonacci number
>40 is done in "real time" (and also e.g. the fibonacci number 100 is
>done in real time; be aware that this is not a built in function). And
>also Omikron Basic 6.3 (Basic for the Macintosh) makes the job in "real
>time". And then I was shocked, because Clean requires 30sec! (and
>curiously calculating the fibonacci number with real number is not
>faster; the opposite is the case; maybe this is due to the fact that my
>Macintosh 603e processor is good for integers).

There are several algorithms to compute Fibonacci numbers. The most naive is:

fib 0 = 1
fib 1 = 1
fib n = fib (n-1) + fib (n-2)

This algorithm has an exponential complexity.

It is also possible to compute Fibonacci numbers in linear time. e.g.

fib n = lin_fib n 1 1
where
	lin_fib :: !Int !Int !Int -> Int
	lin_fib 0 a b = a
	lin_fib n a b = lin_fib (n-1) b (a+b)

>After that I printed out the "Clean Language Report". I found in it that
>it is possible to make a "strict" evaluation. But calculating the
>fibonacci numbers in a strict fashion is n o t faster!

That is because the Clean compiler derives this strictness itself.

>And now for myself I am thrown wheter I should make the next step and
>learn Clean or I should go back to Fortran and Basic (and IDL).

The algorithm used determines the complexity of your program. That is
independent of the language used.

>I often read benchmarks that Clean is not much slower than C. And I am
>not a friend of benchmarking  into the last detail. But what the people
>do in their benchmarks? It is right that write down the code for
>calculating the fibonacci number is much more easier than in Basic or
>Fortran. But if someone needs really fibonacci numbers in a program how
>can he wait 30sec! And in that context how can someone trust in writing
>"real life applications".

In these benchmarks people compare similar algorithms...

-- Pieter Koopman