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

[Dan Weston]

I would be interested in seeing a multithreaded solution, with each 
child thread crossing off the multiples of its own prime. The parent 
thread would be blocked from spawning a new thread for multiples of the 
next prime p until all existing child threads are past p.

It is not clear to me what functional data structure would most 
efficiently accommodate this algorithm, however. Any suggestions?

Dan Weston

apfelmus at quantentunnel.de wrote:
> 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
> 
> _______________________________________________
> Haskell-Cafe mailing list
> Haskell-Cafe at haskell.org
> http://www.haskell.org/mailman/listinfo/haskell-cafe
> 
>