a-conjecture-of-mine

An exercise on polyglossy: the same problem solved on multiple languages

commit 88f3f2cac3e0ac7856d42020878fefa8d9f80af3
parent f6588857c0d90fc3805ea192ec397a1fc45da62b
Author: Gark Garcia <37553739+GarkGarcia@users.noreply.github.com>
Date:   Sat, 18 May 2019 19:44:06 -0300

Implemented concurrency in the Go version.

Diffstat:
MGo/conjecture.go | 88++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++-----------
1 file changed, 76 insertions(+), 12 deletions(-)
diff --git a/Go/conjecture.go b/Go/conjecture.go
@@ -9,6 +9,7 @@ import (
 	"bufio"
 	"fmt"
 	"math"
+	"math/rand"
 	"os"
 	"strconv"
 	"strings"
@@ -16,6 +17,15 @@ import (
 )
 
 func main() {
+	nThreads := uint(1)
+	if len(os.Args) > 0 {
+		if arg, err := strconv.ParseUint(os.Args[0], 10, 32); err == nil {
+			if arg >= 1 {
+				nThreads = uint(arg)
+			}
+		}
+	}
+
 	fmt.Println("\nThis program is a simple test for the following conjecture:")
 	fmt.Println("\nLet S: N -> N be the sum of the digits of a positive integer.")
 	fmt.Println("For all A and B in N, S(A + B) = S(A) + S(B) - 9k, where k is an integer.")
@@ -29,9 +39,9 @@ func main() {
 		max := uint(max)
 
 		fmt.Println("\nLOADING. . .")
-		tuple, found, elepsed := getCounterexample(max)
-		fmt.Printf("LOADED in %dms\n", elepsed.Nanoseconds()/int64(math.Pow10(6)))
+		tuple, found, elepsed := getCounterexample(max, nThreads)
 
+		fmt.Printf("LOADED in %dms\n [%d Go Routines]", elepsed.Nanoseconds()/int64(math.Pow10(6)), nThreads)
 		if !found {
 			fmt.Printf("\nThe conjecture is proved for all natural numbers smaller or equals to %d!\n", max)
 		} else {
@@ -42,29 +52,83 @@ func main() {
 	}
 }
 
-func getCounterexample(max uint) (value [2]uint, found bool, elepsed time.Duration) {
+func getCounterexample(max uint, nThreads uint) (value [2]uint, found bool, elepsed time.Duration) {
 	start := time.Now()
-
 	sums := getSums(max)
-	for a := uint(0); a <= max; a++ {
+	mRange := make([]uint, max+1)
+
+	if nThreads > 1 {
+		channels := make([](chan [2]uint), nThreads)
+
+		// Shuffle the numbers from 0 to max
+		for i, n := range append(rand.Perm(int(max)), 0) {
+			mRange[i] = uint(n)
+		}
+
+		ranges := make([][]uint, nThreads)
+		rangeLen := int((max + 1) / nThreads)
+
+		// Subdivide mRange into nThread sub-ranges
+		for i := 0; i < int(nThreads); i++ {
+			ranges[i] = mRange[i : (i+1)*rangeLen]
+			channels[i] = make(chan [2]uint)
+		}
+
+		for i := rangeLen*int(nThreads) + 1; i <= int(max); i++ {
+			r := &ranges[i%int(nThreads)]
+			*r = append(*r, mRange[i])
+		}
+
+		// Compute the result of each sub-range
+		for i, tRange := range ranges {
+			go getCounterRange(tRange, max, &sums, channels[i])
+		}
+
+		// Listen for the computation to finish
+		for _, c := range channels {
+			for msg := range c {
+				return msg, true, time.Since(start)
+			}
+		}
+	} else {
+		c := make(chan [2]uint)
+
+		for i := range mRange {
+			mRange[i] = uint(i)
+		}
+
+		go getCounterRange(mRange, max, &sums, c)
+		for msg := range c {
+			return msg, true, time.Since(start)
+		}
+	}
+
+	return [2]uint{0, 0}, false, time.Since(start)
+}
+
+func getCounterRange(rang []uint, max uint, sums *[]int, c chan [2]uint) {
+	for _, a := range rang {
 		for b := a; b <= max; b++ {
-			diff := sums[a+b] - sums[a] - sums[b]
+			diff := (*sums)[a+b] - (*sums)[a] - (*sums)[b]
 
 			if diff%9 != 0 {
-				return [2]uint{a, b}, true, time.Since(start)
+				c <- [2]uint{a, b}
+				close(c)
+
+				return
 			}
 		}
 	}
 
-	return [2]uint{0, 0}, false, time.Since(start)
+	close(c)
 }
 
 func getSums(max uint) []int {
-	maxRange := 2 * (max + 1)
-	sums := make([]int, maxRange, maxRange)
+	maxRange := 2*max + 1
+	sums := make([]int, maxRange)
 
-	for i := uint(0); i < maxRange; i++ {
-		sums[i] = sumDigits(i)
+	for i := range sums {
+		sums[i] = sumDigits(uint(i))
 	}
 
 	return sums