[Haskell-cafe] Re: Optimization fun

[ls-haskell-developer-2006 at m-e-leypold.de]

"Rafael Almeida" <almeidaraf at gmail.com> writes:

> I've always found the following definition of the sieve of eratosthenes
> the clearest definition one could write:
>
> sieve [] = []
> sieve (x:xs) = x : sieve [y | y <- xs, y `mod` x /= 0]

> It doesn't perform better than Augustsson's solution. It does fairly
> worse, actually, but it performs way better than Hogg's 13s algorithm.
> It took around 0.1s on my machine.
>
> You should call the function like this
>
> sieve [2..n]
>
> where n is to what number you want to calculate the sieve. I could also
> have used filter instead of the list comprehension.

What you have here, is not a sieve (in my opinion) as any
implementation that uses `mod`. The characteristics of a sieve is,
that it uses the already found primes to generate a list of non-primes
that is then removed from a list of candiates for primeness. The
salient point is, that there should be no test divisions, but rather
only comparisons. In the imperative version the comparisons are
implicit (in the process of marking the array positions), but there
are no test divisions.

A real sieve should look like this (IMHO)

   http://www.etc-network.de/blog/mel/programming/how-to-spend-midnight.html#how-to-spend-midnight

This is my implementation, please, forgive my shameless
self-advertisment :-).


Regards -- Markus