4
\$\begingroup\$

I've found a question on SO (here), which is a prime number generator that uses channels. First of all, I had some trouble to find out how this code works, but later on, I saw the fun of it. Then, all the sudden, I saw the light! The code can be used perfectly to benchmark the difference between channels versus a for loop. The question on SO uses a channel to store the total range of integers, then pulls the numbers one by one to figure out if it's prime or not. So I used my fasted code to calculate a prime number, versus the channel one. The question is, can it be improved?

This is the channel version:

package main

import "fmt"
import "time"

func Generate(ch chan<- int) {
    for i := 2; ; i++ {
        ch <- i
    }
}

func Filter(in <-chan int, out chan<- int, prime int) {
    for {
        i := <-in
        if i%prime != 0 {
            out <- i
        }
    }
}

func main() {
    ch := make(chan int)
    go Generate(ch)
    t0 := time.Now()
    for i := 0; i < 170; i++ {
        prime := <-ch
        fmt.Println(prime)
        ch1 := make(chan int)
        go Filter(ch, ch1, prime)
        ch = ch1
    }
    t1 := time.Now()
    fmt.Printf("The call took %v to run.\n", t1.Sub(t0))
}

This is my own version:

package main

import "fmt"
import "time"

func isPrime(number int) bool {
    switch {
    case number < 2:
        return false
    case number == 2:
        return true
    case number%2 == 0:
        return false
    default:
        for i := 3; (i * i) <= number; i += 2 {
            if number%i == 0 {
                return false
            }
        }
        return true
    }
}

func main() {
    t0 := time.Now()
    for i := 1; i < 1014; i++ {
        if isPrime(i) {
            fmt.Println(i)
        }
    }
    t1 := time.Now()
    fmt.Printf("The call took %v to run.\n", t1.Sub(t0))
}

The channel version runs in 21 ms. My own version runs in 11 ms.

\$\endgroup\$
2
\$\begingroup\$

yes it can be improved.

first, Golang is supposed to be big on concurrency. Your version is not concurrent. It will probably run on just one core.

Channels are supposed to give us concurrency for free. Here, we have a cascade of filtering channels, and while a number makes its way through a later channel, another, bigger number can well enter the earlier channel, concurrently. On multi-core, I'd expect to see high CPU utilization for this code.

The channel version can be drastically improved. Filtering by 7, say, should only be done for numbers from 49 up. There's no need to check 28 by 7—it'll be caught earlier, by a lower prime factor, 2. So the filtering channels should only be started up at primes' squares. This will radically reduce the number of channels working largely for nothing right now. The time complexity should improve from about quadratic to about n1.5, give or take.

I call it the postponement technique. I described it in this SO answer as well as many others. I first thought it up when I worked through the SICP book many years ago and tried re-writing its primes code in Haskell for fun. I thought then it must be widely known... but it turns out, it wasn't.

And of course, there's no need to enumerate any even number above 2. Here's the code:

func Sieve(out chan<- int) {   // 2,000 primes:
  out <- 2                     //  was: 1.32s now: 0.06s
  out <- 3
  q := 9
  ps := make(chan int)
  go Sieve(ps)                 // separate primes supply
  p := <-ps   // p=2, ps@3
  p = <-ps    // p=3, ps@5
  nums := make(chan int)
  go NumsFromBy(5,2,nums)
  for i := 0; ; i++ {
    n := <-nums
    if n < q {
        out <- n   // n is prime
    } else {
        ch1 := make(chan int)
        go Filter(nums, ch1, p)  // p=3
        nums = ch1
        p = <-ps  // 5
        q = p*p   // 25 !
    }
  }
}
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.