This directory describes a neat way to list prime numbers
that uses a large number of concurrent communicating processes.
[ Specification ]
The solution lends itself to coding in Ada (using rendezvous),
Smalltalk (using filters and recursive messages), C using semi-coroutines,
and C using a pipe. Examples of these solutions are in this directory.
Also there are solutions in Smalltalk, C++, Java.
The Prolog code shows a version that is close to Eratsostene's original
concept of listing a lot of numbers and crossing out the non-primes.
Ada using rendezvous and a task type.
[ sieve.ada ]
This directory has the components necesary to experiment with this in Unix:
- p0sh n - generate 2,3,4,5,...n
[ p0sh ]
- ppsh - save first and remove all multiples.
[ p1sh ]
In theory an infinite pipe like this forms the sieve:
In practice you don't need many filters to get a lot of primes:
[ sievesh ]
You can of course code the two shell scripts into C:
[ p0.c ]
[ p1.c ]
and then compile them into p1 amd p2 and
use them in place of p0sh and p1sh.
. . . . . . . . . ( end of section UNIX Shell) <<Contents | End>>
C using restartable code or a semi-co-function
[ sieve.c ]
C++ via a class of Primes.
[ sieve.C ]
[ sieve.cpp ]
A simple version defining a Filter interface:
[ Sieve.java ]
[ Sieve.html ]
Here is an example of programming Java Threads
to work like co-routines (only one runs at a time,
with flow weaving between the individual threads)
It prints out some helpful diagnostics as it runs.
See the code
[ ThreadedSieve.java ]
[ ThreadedSieve.html ]
It is possible to develop a reusable class of
SemiThreads that run as co-routines
[ SemiThread.html ]
derive Hoare's Prime as a special extension:
[ PrimeThread.html ]
Working out the Java code is left as an exercise.
Java provides some ready-made synchronization
primitives: wait(), notify(), and yield(). The use
of these is shown in:
[ ../java/Sieve2.java ]
[ ../java/DataThread.html ]
[ ../java/PrimeThread2.html ]
An untested generic DataThread can be found in:
[ ../java/DataThread2.java ]
Does it work?
Java has a low level version of the UNIX pipe
that is ideal for buffered message passing between threads.
Each pipe has two ends: a PipedInputStream and
a PipedOutputStream. The pipe is created by connecting
these together. See the code
[ PipedSieve.java ]
[ PipedSieve.html ]
[ PrimeFilter.html ]
[ Filter.html ]
. . . . . . . . . ( end of section Java) <<Contents | End>>
Smalltalk using filters and generators:
[ sieve.st ]
Why not take this same concept and map it onto one of out GPU systems?
Prolog using a dynamic database of primes:
[ sieve.plg ]
[ ../c/primes.c ]
[ ../lisp/primes.lsp ]
[ ../prolog/primes.plg ]
[ ../prolog/primes2.plg ]
[ ../sebesta/primes0.ada ]
. . . . . . . . . ( end of section Index to Solutions to Eratosthene's Sieve) <<Contents | End>>