Parallel Sieve of Eratosthenes

From CodeCodex

The Sieve of Eratosthenes is a very old algorithm for generating the sequence of prime numbers.

It is also possible to reformulate the algorithm as a communicating pipeline of concurrent processes. In this form, the first process creates the second process, and sends it the sequence of integers starting from 2 (the first prime). The second and subsequent processes each operate as follows:

  • Read the first integer from the parent process. Output it as prime, and also save it for later.
  • Create a child process to receive subsequent output.
  • Read the remaining integers from the parent process. Discard each one that is an exact multiple of the first integer. Pass the rest to the child process.

Ada[edit]

Here is a version using tasks in Ada:

with Ada.Text_IO;
use Ada;         
procedure parasieve1 is

    task type child is

        entry next_int(i : integer);

    end child;

    subtype offspring is child;
      -- need another name because "child" within child refers to
      -- current task, not to the type

    task body child is

        my_prime : integer;
        subchild : access offspring;

    begin
        accept next_int(i : integer) do
            my_prime := i;
            Text_IO.Put_line(integer'image(my_prime));
        end next_int;
        subchild := new offspring;
        loop
            accept next_int(i : integer) do
                if i mod my_prime /= 0 then
                    subchild.next_int(i);
                end if;
            end next_int;
        end loop;
    end child;

    first_child : child;
    i : integer;

begin -- parasieve1
    i := 1;
    loop
        i := i + 1;
        first_child.next_int(i);
    end loop;
end parasieve1;

Here is another Ada version, using the protected types introduced in Ada95:

with Ada.Text_IO;
use Ada;         
procedure parasieve2 is

    protected type int_buffer is

        entry put(i : in integer);
        entry get(i : out integer);

    private
        last_i : integer;
        got_i : boolean := false;
    end int_buffer;              

    protected body int_buffer is

        entry put(i : in integer) when not got_i is
        begin                                      
            last_i := i;                           
            got_i := true;                         
        end put;                                   

        entry get(i : out integer) when got_i is
        begin                                   
            i := last_i;                        
            got_i := false;                     
        end get;                                

    end int_buffer;

    type int_buffer_ptr is access int_buffer;

    task type child(from_parent : int_buffer_ptr) is
    end child;

    subtype offspring is child;
      -- need another name because "child" within child refers to
      -- current task, not to the type

    task body child is

        my_prime, i : integer;
        subchild : access offspring;
        to_child : int_buffer_ptr;

    begin
        from_parent.get(my_prime);
        Text_IO.Put_line(integer'image(my_prime));
        to_child := new int_buffer;
        subchild := new offspring(to_child);
        loop
            from_parent.get(i);
            if i mod my_prime /= 0 then
                to_child.put(i);
            end if;
        end loop;
    end child;

    to_first_child : int_buffer_ptr;
    first_child : access child;
    i : integer;

begin -- parasieve2
    i := 1;
    to_first_child := new int_buffer;
    first_child := new child(to_first_child);
    loop
        i := i + 1;
        to_first_child.put(i);
    end loop;
end parasieve2;

Algol 68[edit]

MODE BUFFER = STRUCT                            
  (                                             
    SEMA full,                                   
    SEMA empty,                                  
    REF INT n                                    
  );                                             

PROC produce = (BUFFER b, INT n) VOID :
    BEGIN                              
        DOWN empty OF b;                                    
        n OF b := n;                                        
        UP full OF b                                                 
    END;                                                             

PROC consume = (BUFFER b) INT :
    BEGIN
        DOWN full OF b;
        INT n = n OF b;
        UP empty OF b;
        n
    END;

PROC sieve = (BUFFER from parent) VOID :
    BEGIN
        INT n = consume(from parent);
        print((" => ", n, new line));
        BUFFER to child = (LEVEL 0, LEVEL 1, HEAP INT);
        PAR BEGIN
            DO
                INT i = consume(from parent);
                IF i MOD n /= 0 THEN
                    produce(to child, i)
                FI
            OD,
            sieve(to child)
        END
    END;


BEGIN
    BUFFER to first child = (LEVEL 0, LEVEL 1, HEAP INT);
    INT n := 1;
    PAR BEGIN
        DO
            n := n + 1;
            produce(to first child, n)
        OD,
        sieve(to first child)
    END
END

Bash[edit]

This can also be implemented in a Bash script as follows:

#!/bin/bash

if test x$1 != x; then
    read start
    echo $start
    while true; do
        read num
        if test x$num == x; then
            break
        fi
        echo "if ("$num" % "$start" != 0) { print "$num', "\n" }' | bc
    done | $0 $1
else
    num=1
    while true; do
        num=$(echo $num + 1 | bc)
        echo $num
    done | $0 xxx
fi

Invoke this script without any arguments to start off the whole chain; it invokes itself with a dummy argument to create each child process. The sequence of primes is sent, one to a line, to standard output. When you've seen enough, hit CTRL/C, and the whole chain of processes should shut itself gracefully down. Note the use of bc(1) to handle all the arithmetic; this is arguably a little optimistic.

Warning: this script will create a new process for every prime number found. This can rapidly add up to a lot of processes, which can slow your system down or affect important services. Don't run it on a machine where you might inconvenience other users.