Background: I am trying to implement a logic which find the smallest positive number that is evenly divisible by all of the numbers from 1 to 20. I have implemented a sequential version and got an answer as 232792560.
Question: When I try to build some concurrency on this problem ( see uncommented block of code), it does run but never shows any result. Can anyone of you guide me on where I am going wrong?
Note: I am very much new to golang; and I am aware that, this is not the best problem for concurrency since there is no guarantee that I will have the smallest positive number as first result. However, I tried it out of my curiosity.
package main
import(
"fmt"
)
func divide(num int) bool {
for i := 1; i <= 20; i++ {
if num % i != 0 {
return false
}
}
return true
}
func main() {
num:=0
//simple function
/*for {
num++;
result := divide(num)
if result {
fmt.Println("Smallest number is: ", num)
break
}
}*/
//go-routine
//go-routine
var wg sync.WaitGroup
for {
num++;
wg.Add(1)
go func(x int) {
result := divide(x)
if result {
fmt.Println("Smallest number is: ", x)
defer wg.Done()
}
}(num)
}
wg.Wait()
fmt.Println("End.")
}
It doesn't make sense to launch unlimited number of goroutines - it will be performing worse, than non-concurrent solution. You can try to use a "worker pool" pattern and batch the calculations.
package main
import (
"fmt"
"runtime"
)
func divide(num int) bool {
for i := 1; i <= 20; i++ {
if num%i != 0 {
return false
}
}
return true
}
const step = 100000
func main() {
result := make(chan int)
jobs := make(chan int)
for w := 0; w < runtime.NumCPU(); w++ {
go func() {
for n := range jobs {
for i := n; i < n+step; i++ {
if divide(i) {
result <- i
}
}
}
}()
}
num := 1
for {
select {
case jobs <- num:
num += step
case x := <-result:
fmt.Println("Smallest number is:", x)
return
}
}
}
A different approach to your problem would be filters. The idea is to chain a bunch of goroutines with channels and make them filter all values that don't pass some test. In your case you want to filter numbers that are not evenly divisible by some number. This is how it looks:
package main
import (
"fmt"
)
func main() {
in := make(chan int)
tmp := in
// Create filter-goroutines
for i := 1; i <= 20; i++ {
tmp = makeDivisor(i, tmp)
}
running := true
// Now feed in all the numbers...
for i := 1; running; i++ {
select {
// Check if a number passed all filters.
case k := <-tmp:
fmt.Printf("Answer is %d
", k)
close(in)
running = false
// Otherwise feed in the next.
case in <- i:
}
}
}
func makeDivisor(n int, c chan int) chan int {
cc := make(chan int)
go func() {
for i := range c {
if i%n == 0 {
cc <- i
}
}
close(cc)
}()
return cc
}
Here it is on the playground. (Note that the playground won't work with 20 filters, but try it locally too.)
Note that the first filters have much more work to do than the ones further into the chain. You could launch more of the first filters to solve this, although the integer-division is pretty fast and this whole thing might be limited by channel communication at the moment.
Does it work?
Answer is 232792560
Yes.