Index to Solutions to Eratosthene's Sieve

Introduction

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

Ada using rendezvous and a task type. [ sieve.ada ]

Unix Shell

This directory has the components necesary to experiment with this in Unix:
1. p0sh n - generate 2,3,4,5,...n //www/dick/cs320/sieve/p0sh
2. ppsh - save first and remove all multiples. //www/dick/cs320/sieve/p1sh

   In theory an infinite pipe like this forms the sieve:

3. p0sh|p1sh|p1sh|p1sh|p1sh|... In practice you don't need many filters to get a lot of primes: [ sievesh ]

   Unix Shell and C

   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 | Index>>

C

C using restartable code or a semi-co-function [ sieve.c ]

C++

C++ via a class of Primes. [ sieve.C ]

Java

Simple Sieve

A simple version defining a Filter interface: [ Sieve.java ] and documentation [ Sieve.html ]

Co-Routine Style

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 ] plus documentation [ ThreadedSieve.html ]

It is possible to develop a reusable class of SemiThreads that run as co-routines [ SemiThread.html ] and then derive Hoare's Prime as a special extension: [ PrimeThread.html ] Working out the Java code is left as an exercise.

Synchronization

Java provides some ready-made synchronization primitives: wait(), notify(), and yield(). The use of these is shown in: [ Sieve2.java ] with documentation in [ DataThread.html ] and [ PrimeThread2.html ]

An untested generic DataThread can be found in: [ DataThread2.java ] Does it work?

Pipes

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 ] and documentation: [ PipedSieve.html ] [ PrimeFilter.html ] and [ Filter.html ]

. . . . . . . . . ( end of section Java) <<Contents | Index>>

Smalltalk

Smalltalk using filters and generators: [ sieve.st ]

Invitation

Why not take this same concept and map it onto one of our local supercomputer architectures - Challenge, The Hypercube, ...?

Other Prime Number Generators

Prolog

Prolog using a dynamic database of primes: [ sieve.plg ]

C [ primes.c ] LISP [ primes.lsp ] Prolog [ primes.plg ] [ primes2.plg ] Ada [ primes0.ada ]

. . . . . . . . . ( end of section Index to Solutions to Eratosthene's Sieve) <<Contents | Index>>