a-conjecture-of-mine

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

git clone: git://git.pablopie.xyz/a-conjecture-of-mine
Log
Files
Refs

Commit: 3fd6bd1adb62ee1365a27e075a514bb28f3f2ed3
Parent: 64c1ff4ad588df2ce4d12fd7d5a770a7e07f7527
Author: Pablo Escobar Gaviria <gark.garcia@protonmail.com>
Date: Sat, 11 Jan 2020 17:29:58 -0200

Updated the Rust and the Go implementations to fit the new algorthm.

Unfortunatelly the Rust implementation is now much slower and the Go implementation is broken.

Diffstat

2 files changed, 129 insertions, 120 deletions

Status	File Name	N° Changes	Insertions	Deletions
Deleted	Go/conjecture.go	120	0	120
Added	Go/main.go	129	129	0

diff --git a/Go/conjecture.go b/Go/conjecture.go
@@ -1,120 +0,0 @@
-package main
-
-// This program is a simple test for the following conjecture:
-
-// Let S: N -> N be the sum of the digits of a positive integer.
-// For all A and B in N, S(A + B) = S(A) + S(B) - 9k, where k is an interger.
-
-import (
-	"os"
-	"strconv"
-)
-
-type iter struct {
-	Start    uint
-	Max      uint
-	Interval uint
-}
-
-const success = 0
-const fail = 1
-const invalidInput = 2
-
-func main() {
-	if len(os.Args) > 0 {
-		nThreads := uint(1)
-
-		if len(os.Args) > 1 {
-			if arg, err := strconv.ParseUint(os.Args[2], 10, 64); err == nil && arg >= 1 {
-				nThreads = uint(arg)
-			}
-		}
-
-		if max, err := strconv.ParseUint(os.Args[0], 10, 64); err == nil {
-			if getCounterexample(uint(max), nThreads) {
-				os.Exit(fail)
-			} else {
-				os.Exit(success)
-			}
-		} else {
-			os.Exit(invalidInput)
-		}
-	} else {
-		os.Exit(invalidInput)
-	}
-
-}
-
-func getCounterexample(max uint, nThreads uint) bool {
-	sums := getSums(max)
-
-	if nThreads > 1 {
-		channels := make([](chan bool), nThreads)
-
-		// Compute the result of each sub-range
-		for i := 0; i < int(nThreads); i++ {
-			channels[i] = make(chan bool)
-			it := iter{uint(i), max, nThreads}
-
-			go getCounterIter(it, &sums, channels[i])
-		}
-
-		// Listen for the computation to finish
-		for _, c := range channels {
-			if msg := <-c; msg {
-				return true
-			}
-		}
-	} else {
-		c := make(chan bool)
-		it := iter{0, max, 1}
-
-		go getCounterIter(it, &sums, c)
-
-		return <-c
-	}
-
-	return false
-}
-
-func getCounterIter(it iter, sums *[]int, c chan bool) {
-	for a := it.Start; a <= it.Max; a += it.Interval {
-		for b := a; b <= it.Max; b++ {
-			diff := (*sums)[a+b] - (*sums)[a] - (*sums)[b]
-
-			if diff%9 != 0 {
-				c <- true
-				close(c)
-
-				return
-			}
-		}
-	}
-
-	c <- false
-	close(c)
-}
-
-func getSums(max uint) []int {
-	maxRange := 2*max + 1
-	sums := make([]int, maxRange)
-
-	for i := range sums {
-		sums[i] = sumDigits(uint(i))
-	}
-
-	return sums
-}
-
-func sumDigits(n uint) int {
-	var sum uint
-
-	for {
-		if n <= 0 {
-			return int(sum)
-		}
-
-		sum += n % 10
-		n /= 10
-	}
-}

diff --git a/Go/main.go b/Go/main.go
@@ -0,0 +1,129 @@
+package main
+
+// This program is a simple test for the following conjecture:
+
+// Let S: N -> N be the sum of the digits of a positive integer.
+// For all A and B in N, S(A + B) = S(A) + S(B) - 9k, where k is an interger.
+
+import (
+	"os"
+	"strconv"
+        "sync"
+)
+
+const success = 0
+const fail = 1
+const invalidInput = 2
+
+var lock = sync.RWMutex{}
+var sumsCache = map[uint]int{}
+var max uint = 1
+var nGoRoutines uint = 1
+
+func main() {
+	if len(os.Args) > 0 {
+		if len(os.Args) > 1 {
+			if arg, err := strconv.ParseUint(os.Args[2], 10, 64); err == nil && arg >= 1 {
+				nGoRoutines = uint(arg)
+			}
+		}
+
+		if val, err := strconv.ParseUint(os.Args[0], 10, 64); err == nil {
+                        max = uint(val)
+
+			if counterexample() {
+				os.Exit(fail)
+			} else {
+				os.Exit(success)
+			}
+		} else {
+			os.Exit(invalidInput)
+		}
+	} else {
+		os.Exit(invalidInput)
+	}
+
+}
+
+func counterexample() bool {
+	if nGoRoutines > 1 {
+		channels := make([](chan bool), nGoRoutines)
+
+		// Compute the result of each sub-range
+		for i := uint(0); i < nGoRoutines; i++ {
+			channels[i] = make(chan bool)
+			go counterIter(i, channels[i])
+		}
+
+		// Listen for the computation to finish
+		for _, c := range channels {
+			if msg := <-c; msg {
+				return true
+			}
+		}
+	} else {
+		c := make(chan bool)
+		go counterIter(0, c)
+
+		return <-c
+	}
+
+	return false
+}
+
+func counterIter(start uint, c chan bool) {
+	for a := start; a <= max; a += nGoRoutines {
+		for b := a; b <= max; b++ {
+                        sumAB := lookupOrInsert(a + b)
+                        sumA  := lookupOrInsert(a)
+                        sumB  := lookupOrInsert(b)
+			diff  := sumAB - sumA - sumB
+
+			if diff%9 != 0 {
+				c <- true
+				close(c)
+
+				return
+			}
+		}
+	}
+
+	c <- false
+	close(c)
+}
+
+// Searches for the value of `sumDigits(n)` in the global
+// `sumsCache` store.
+// If the value is found, it gets returned.
+// Otherwise, the value is calculated, stored and then returned.
+func lookupOrInsert(n uint) int {
+    lock.RLock()
+    defer lock.RUnlock()
+    sumN, included := sumsCache[n]
+
+    if included {
+        return sumN
+    }
+
+    sumN = sumDigits(n)
+
+    lock.Lock()
+    defer lock.Unlock()
+    sumsCache[n] = sumN
+
+    return sumN
+}
+
+func sumDigits(n uint) int {
+	var sum uint
+
+	for {
+		if n == 0 {
+			return int(sum)
+		}
+
+		sum += n % 10
+		n /= 10
+	}
+}
+