diff options
author | Moritz Poldrack | 2021-04-14 09:55:37 +0200 |
---|---|---|
committer | Moritz Poldrack | 2021-04-14 09:55:37 +0200 |
commit | 5db9f0e7d77720ef6c7d54720afeddfeec4e3a85 (patch) | |
tree | 92e1faf953a80a4967fa2600724da5a7bbe5f49c /gcd/gcd.go | |
parent | 02082c863dc7912b93013545bd7a2c194691167b (diff) |
added a stupidly over-engineered gcd solution
at least it's multithreaded
Diffstat (limited to 'gcd/gcd.go')
-rw-r--r-- | gcd/gcd.go | 93 |
1 files changed, 93 insertions, 0 deletions
diff --git a/gcd/gcd.go b/gcd/gcd.go new file mode 100644 index 0000000..562e53b --- /dev/null +++ b/gcd/gcd.go @@ -0,0 +1,93 @@ +package main + +import ( + "fmt" + "math" + "os" + "strconv" + "sync" +) + +func main() { + if len(os.Args) != 3 { + fmt.Println("we need 2 numbers. usage: ./gcd 200 50") + os.Exit(2) + } + a, err := strconv.Atoi(os.Args[1]) + if err != nil { + fmt.Printf("whatever %s is… I can't make it an integer: %v\n", os.Args[1], err) + os.Exit(1) + } + b, err := strconv.Atoi(os.Args[2]) + if err != nil { + fmt.Printf("whatever %s is… I can't make it an integer: %v\n", os.Args[2], err) + os.Exit(1) + } + + fmt.Println(gcd(a, b)) +} + +func gcd(a, b int) int { + if a == 0 || b == 0 { + return 0 + } + + adiv := make(chan []int) + bdiv := make(chan []int) + + go getDivisors(a, adiv) + go getDivisors(b, bdiv) + + adivs := <-adiv + bdivs := <-bdiv + + var gcd int + + for i := 0; i < len(adivs); i++ { + for j := 0; j < len(bdivs); j++ { + if adivs[i] == bdivs[j] && adivs[i] > gcd { + gcd = adivs[i] + } + } + } + + return gcd +} + +func getDivisors(num int, out chan []int) { + results := make(chan int, 4096) + joined := make(chan struct{}) + var res []int + var wg sync.WaitGroup + + go func(r chan int) { + for i := range r { + res = append(res, i) + } + joined <- struct{}{} + }(results) + + concurrency := int(math.Ceil(float64(num) / 512)) + + for i := 0; i < concurrency; i++ { + wg.Add(1) + go func(n, l, u int) { + defer wg.Done() + getDivisorsLimit(n, l, u, results) + }(num, i*512+1, i*512+512) + } + + wg.Wait() + close(results) + <-joined + + out <- res +} + +func getDivisorsLimit(num, lowerBound, upperBound int, results chan int) { + for i := lowerBound; i <= upperBound && i <= num; i++ { + if num%i == 0 { + results <- i + } + } +} |