After reading up on the prime sieve, and playing with Go for the past week I thought needed to implement this algorithm in Go and make it parallel.

I want to create a set (n in 2..N) goroutines. Each of these routines will check if it can divide a number (i) by n (integer division). If so the number i is not prime, otherwise it is given to the next goroutine. Communication between the goroutines is done via channels as in this example.

Sieve⌗

In this small example I have 5 goroutines, and we give it the number 3 and 4. The table shows the reminder when dividing by n.

            n = 2   3   4   5  ... ...
-------------------------------------------
i  = 3 % n	    1   0   3   3   3	3   ...
i  = 4 % n	    0   1   0   4   4	3   ...

From here we see that i = 3 is prime, because it has an 1 in the column where n = 2, i = 4 is not prime, because it has a zero in the column where n = 2.

The algorithm for each goroutine thus becomes (in pseudo code):

function(n, i) {
if i == 0 then copy to next goroutine; return
if n >= i then copy to next goroutine; return

// test for primeness, if not prime return the *magic* 
// number 0
if i % n == 0 then
    // not prime
    give 0 to the next goroutine
fi

give i to the next goroutine
}

Or in Go’s syntax:

func f(left, right chan int, n int) {
    i := <-right;
    if i == 0 || n >= i {
	    left <- i;
	    return;
    }
    if i%n == 0 {
	    // too bad
	    left <- 0;
	    return;
    }
    left <- i;
}

Main⌗

The rest of the Go program should setup the goroutines, channels and handle the flags. N - 1 goroutines are set up, and each is connected to its neighbor.

Even nicer would be to really do this in parallel, i.e. send i to all goroutines, and then just see if one of them returned zero. If none of them do, its a prime. For now the following must suffice.

In Go code:

leftmost := make(chan int);
var left, right chan int = nil, leftmost;
for n := 0; n < *prime-1; n++ {
    left, right = right, make(chan int);
    go f(left, right, *prime-n);
}
right <- *prime;        // bang!
x := <-leftmost;        // wait for completion
fmt.Println(x);

This outputs 0 when the number tested is not prime, it outputs the number itself given when it is prime.

% ./sieve -p 32
0			# not prime

% ./sieve -p 11
11			# prime ;-)

Complete listing⌗

package main

import (
    "flag";
    "fmt";
    "os";
)

var prime = flag.Int("p", 13, "test for primeness")

func f(left, right chan int, n int) {
    i := <-right;
    if i == 0 || n >= i { 
	    left <- i;
	    return;
    }   
    if i%n == 0 { 
	    // too bad
	    left <- 0;
	    return;
    }   
    left <- i;
}

func main() {
    flag.Parse();

    if *prime < 2 { 
	    fmt.Fprint(os.Stderr, "You know this already\n");
	    os.Exit(1);
    }   

    leftmost := make(chan int);
    var left, right chan int = nil, leftmost;
    for n := 0; n < *prime-1; n++ {
	    left, right = right, make(chan int);
	    go f(left, right, *prime-n);
    }   
    right <- *prime;        // bang!
    x := <-leftmost;        // wait for completion
    fmt.Println(x);
}