The Sieve of Eratosthene

Some history

One of the oldest and simplest yet interesting algorithm that involves arbitrary large data is the sieve of Eratosthene.

Eratosthene (Cyrene circa 284 BC - Alexandria circa 192 BC) was a great greek mathematician. He was the very first to accurately compute the circumference of Earth, and he invented this clever algorithm to find prime numbers.

In the computing world, this algorithm was once used as a speed "benchmark" for languages and compilers (which is stupid both in the first case, because by inlining arbitrary many steps of the sieve, you could speed the whole thing arbitrarily anyway, and in the second case, as the sieve would eventually be specifically recognized by compilers to speed up benchmarks).

Here we use it not to benchmark speed, but to illustrate language expressiveness.

The Mathematical Idea

Some definitions:

Then we have these preliminary lemmas:

Thus here is the algorithm invented by Eratosthene:

Programming the sieve

The idea of the sieve is relatively simple; but even then, you can write infinitely many programs based on this idea. Existing computer languages would require you to rewrite each from scratch. But in the same way as a human doesn't re-learn the sieve from scratch each time he sees it, we can and should have computers understand it once and for all. Here is how we could do:

The sieve program in various programming languages and paradigms

Lame C-language Version

char * sieve (int max)
{
  int n, n2, m;
  char * sieved ;

  /* malloc'ing */
  sieved = malloc(max) ;
  assert(sieved) ;
  memset(sieved,0,max) ;

  /* loop */
  for (n = 2, n2 = 4; n2<=max ; n2+=(n++<<1)+1 ) {
      if (!sieved[n]) {
        out(n) ;
        for (m=n2; m <= max ;m+=n) sieved[m] = 1 ;
    }
  }
  return sieved ;
}

Here are many reasons why C is a disadvantage, that we can see in this program:

To conclude, it's impossible to express efficiently the generic algorithm in a one C program.

Side-Effecting Message-Passing Version

var	n : int = 2 ;
	sieved : int->bool = function x|->false ;
fun step () =
  if not sieved (n) then
    begin
      out(n) ;
      sieved := function x|-> (old sieved x) or (n divides x)
    end ;
loop
  begin
    step () ;
    increment(n)
  end ;

Pure lazy functional version

let Eratosthene's_Sieve =
   let rec step n sieved =
      let next_num = n+1 in
	 if not (sieved num)
	   then
	      let new_sieved m = (sieved m) or (n divides m) in
		 cons_stream n (step next_num new_sieved)
	   else step next_num sieved in
   prime_stream = step 2 (fun x->false)

"Natural language" version

Consider knowing a natural number n to not be a prime as being false.
Consider number two.
A sieve step is
  if the considered natural number is not known to not be a prime,
    then
	say that the considered natural number is prime, and
	consider knowing a natural number not to be a prime as
	  previously knowing that and the considered natural number
	   not dividing this one.
To sieve is to loop on the sieve step, each time considering the next number.
Recursively export the verb to sieve.

Less capable natural language interpreters may require a more thorough quoting, parenthesing, annotating and explicit typing than otherwise.

Variations on the sieve

Here are things we could tell the system so it can enhance the implementation of the sieve:

Efficiency annotations:

Input/Output annotations

To Do: