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
[EMAIL PROTECTED] 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@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
