[Haskell-cafe] Re: Genuine Eratosthenes sieve [Was: Optimization fun]

[apfelmus at quantentunnel.de]

Jens Blanck wrote:
>>
>> The point about "Eratosthenes's sieve" is that it does not specify
>> algorithmically how to find the next number to be crossed. It does not
>> even define how to store (crossed) numbers, it stores them "on paper".
> 
> But , I believe that Eratosthenes's sieve does specify how to store numbers
> and how to find the next to cross out.
> 
> This is how I remember it:
> 
> 0 List the numbers from 2 onwards.
> 1 Take first uncrossed number, say p.
> 2 Cross every pth number from there on (crossed or not).
> 3 Repeat from 1.

And where's the storage specification? :)

What I'd like to say is that in step 0, "list the numbers" may mean many
things to the computer. For example, it can list them in a plain list or
a finite map or a priority queue (or an array for the imperative).
Yitzchaks 'deleteOrd' sieve uses a plain list whereas Melissa stores the
crossed numbers in a priority queue. The choice has impact on how fast
you can find the next number to be crossed: Yitzchak needs linear time
whereas Melissa can do in logarithmic time. Here, time is parametrized
by the count of primes smaller than the current number considered.

In the end, the computer needs a more detailed description than the
human who can see and cross numbers on a piece of paper at his choice.

Regards,
apfelmus