Concurrent Sieve of Eratosthenes in GO

Disclaimer
  • We show how to program a concurrent Sieve of Eratosthenes in GO. We use filter routines that closely mimic the sieving in the algorithm.
  • concurrentPipelineSieve.go consists of a pipeline mode up of of a source, √N channels, √N-1 filters and a sink, as shown for N = 25.
  • In this case N is the limit to which we sieve. The number of channels = √N, (line 53).
  • An array of √N chans called channel is created in line 55-56.
/*concurrentPipelineSieve.go*/
package main
import ( "fmt"; "math"; "os"; "strconv"; "time")

var done = make(chan bool)

func source(p chan int, N int) {
   for i := 2; i <= N; i++ {
      p <- i
   }
   close(p)
}

func filter(index int, 
     in chan int, out chan int) {
   var ( counter = 0; prime   int)
   for {
      val, open := <-in
      if !open {
         close(out)
         return
      }
      switch {
      case (counter <= index):
         out <- val
         if counter == index {
            prime = val
         }
      default:
         if val%prime != 0 {
            out <- val
         }
      }
      counter++
   }
}

func sink(p chan int, count *int) {
   for {
      val, open := <-p
      if !open {
         done <- true
         return
      } else {
         //fmt.Println(val)
         *count++
      }
   }
}

func main() {
   N, _ := strconv.Atoi(os.Args[1])
   numChannels := 
      int((math.Sqrt(float64(N))))
   var channel = 
      make([]chan int, numChannels)
   start := time.Now()
   for p := 0; p < numChannels; p++ {
      channel[p] = make(chan int)
   }
   go source(channel[0], N)
   for i := 0; i < numChannels-1; i++ {
      go filter(i, channel[i], 
                   channel[i+1])
   }
   var count = 0
   go sink(channel[numChannels-1],
          &count)
   <-done
   elapse := time.Since(start)
   fmt.Println(count, 
      elapse.Microseconds())
}

Function source (lines 7-12) generates the numbers 2,3,4,…,N and pumps them out to channel[0].
line 14: function filter is where the main action of this program takes place.
line 17-20: It attempts to open the in channel. If it fails, it closes the out channel and terminates.
The for loop in filter increments counter for each value received from in. If counter ≤ index of filter, it simply passes the filter through to out.

However, if counter==index, val is a new prime.
If counter > index, we suppress all multiples of prime from the output.
This fulfills the requirements of filtering as shown in the above diagram.
Each goroutine in this program passes through only as many integers as are needed.

Function sink (lines 38–49) consumes the numbers output by the last channel, i.e. channel[√N-1].
We can print out the primes here (line 45), but we simply count the primes at the moment.

sink signals that all work is completed (the input channel is closed, lines 42–43) through the variable done.

The pipeline of √N-1 filters operate concurrently and correspond to the sieving operations of the basic algorithm.

GO home
Next