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: 4a8f41f1ee7d2bc408a466941c5b3d889324f821
Parent: 23c7444ae60da434cfd3337e1766869eaa087306
Author: Pablo Escobar Gaviria <gark.garcia@protonmail.com>
Date: Tue, 21 Jan 2020 08:17:16 -0200

Cleaned the C and the Rust implementations.

Diffstat

7 files changed, 146 insertions, 212 deletions

Status	File Name	N° Changes	Insertions	Deletions
Modified	C/main.c	70	26	44
Modified	Go/main.go	12	7	5
Modified	Kotlin/main.kt	3	1	2
Deleted	Rust/Cargo.lock	25	0	25
Deleted	Rust/Cargo.toml	8	0	8
Added	Rust/main.rs	112	112	0
Deleted	Rust/src/main.rs	128	0	128

diff --git a/C/main.c b/C/main.c
@@ -30,38 +30,8 @@ typedef struct
 {
     int start;
     int step;
-} iter_info;
-
-// Find the number of processors on host machine
-int get_num_cores()
-{
-#ifdef WIN32
-    SYSTEM_INFO sysinfo;
-    GetSystemInfo(&sysinfo);
-    return sysinfo.dwNumberOfProcessors;
-#elif MACOS
-    int nm[2];
-    size_t len = 4;
-    uint32_t count;
-
-    nm[0] = CTL_HW;
-    nm[1] = HW_AVAILCPU;
-    sysctl(nm, 2, &count, &len, NULL, 0);
-
-    if (count < 1)
-    {
-        nm[1] = HW_NCPU;
-        sysctl(nm, 2, &count, &len, NULL, 0);
-        if (count < 1)
-        {
-            count = 1;
-        }
-    }
-    return count;
-#else
-    return sysconf(_SC_NPROCESSORS_ONLN);
-#endif
-}
+    int end;
+} range;
 
 int sum_digits(unsigned n)
 {
@@ -76,9 +46,10 @@ int sum_digits(unsigned n)
     return sum;
 }
 
-int get_counterexpl_iter(iter_info *iter)
+// Searches for a counterexample in an specific range.
+int counterexempl(range *r)
 {
-    for (int a = iter->start; a <= max; a += iter->step)
+    for (int a = r->start; a <= r->end; a += r->step)
         for (int b = a; b <= max; b++)
         {
             if ((sums_cache[a + b] - (sums_cache[a] + sums_cache[b])) % 9 != 0)
@@ -95,26 +66,37 @@ int main(int argc, char *argv[])
 {
     if (argc > 1)
     {
-        max = strtoul(argv[1], NULL, 10);
-	if (max <= 0) return INVALID_INPUT;
+        unsigned int max = strtoul(argv[1], NULL, 10);
+	if (!max) return INVALID_INPUT;
+
+        unsigned int n_threads = 1;
+        if (argc > 2)
+        {
+            n_threads = strtoul(argv[2], NULL, 10);
+            if (!n_threads) return INVALID_INPUT;
+        }
 
-        int n_threads = get_num_cores();
         pthread_t thread_ids[n_threads];
-        iter_info thread_iters[n_threads];
+        range thread_ranges[n_threads];
 
         // Create the sums cache
-        int sums_c = 2 * max;
-        sums_cache = malloc(sizeof(int) * sums_c * 2); //original (sizeof(int)* sums_c) causing seg faults in multi-threading
+        // Original (2 * max) causing seg faults in multi-threading
+        int sums_c = 3 * max;
+        sums_cache = malloc(sizeof(int) * sums_c);
         for (int i = 0; i <= sums_c; i++)
             sums_cache[i] = sum_digits(i);
 
 
-        // Create the threads, divide the task into number of threads equivalent to number
-        // of cores on the host machine
+        // Divide the task into the specified number of threads 
         for (int i = 0; i < n_threads; i++)
         {
-	    thread_iters[i] = (iter_info){i, n_threads};
-            err = pthread_create(&thread_ids[i], NULL, get_counterexpl_iter, &thread_iters[i]);
+	    thread_ranges[i] = (range){i, n_threads, max};
+            err = pthread_create(
+                &thread_ids[i],
+                NULL, 
+                counterexempl, 
+                &thread_ranges[i]
+            );
 
             if (err) fprintf(stderr, "Unable to create thread : %d\n", err);
         }

diff --git a/Go/main.go b/Go/main.go
@@ -11,9 +11,9 @@ import (
 )
 
 type iter struct {
-	Start    uint
-	End      uint
-	Step uint
+	Start uint
+	End   uint
+	Step  uint
 }
 
 const success = 0
@@ -25,12 +25,14 @@ func main() {
 		var nGoRoutines uint = 1
 
 		if len(os.Args) > 1 {
-			if arg, err := strconv.ParseUint(os.Args[2], 10, 64); err == nil && arg >= 1 {
+                        arg, err := strconv.ParseUint(os.Args[2], 10, 64)
+			if err == nil && arg >= 1 {
 				nGoRoutines = uint(arg)
 			}
 		}
 
-		if max, err := strconv.ParseUint(os.Args[0], 10, 64); err == nil {
+                max, err := strconv.ParseUint(os.Args[0], 10, 64)
+		if err == nil {
 			if counterexample(uint(max), nGoRoutines) {
 				os.Exit(fail)
 			} else {

diff --git a/Kotlin/main.kt b/Kotlin/main.kt
@@ -74,4 +74,4 @@ fun HashMap<Int, Int>.getSum(key: Int): Int {
 
         return value
     }
-}-
\ No newline at end of file
+}

diff --git a/Rust/Cargo.lock b/Rust/Cargo.lock
@@ -1,25 +0,0 @@
-# This file is automatically @generated by Cargo.
-# It is not intended for manual editing.
-[[package]]
-name = "digital_sum"
-version = "0.1.0"
-dependencies = [
- "num_cpus 1.8.0 (registry+https://github.com/rust-lang/crates.io-index)",
-]
-
-[[package]]
-name = "libc"
-version = "0.2.44"
-source = "registry+https://github.com/rust-lang/crates.io-index"
-
-[[package]]
-name = "num_cpus"
-version = "1.8.0"
-source = "registry+https://github.com/rust-lang/crates.io-index"
-dependencies = [
- "libc 0.2.44 (registry+https://github.com/rust-lang/crates.io-index)",
-]
-
-[metadata]
-"checksum libc 0.2.44 (registry+https://github.com/rust-lang/crates.io-index)" = "10923947f84a519a45c8fefb7dd1b3e8c08747993381adee176d7a82b4195311"
-"checksum num_cpus 1.8.0 (registry+https://github.com/rust-lang/crates.io-index)" = "c51a3322e4bca9d212ad9a158a02abc6934d005490c054a2778df73a70aa0a30"

diff --git a/Rust/Cargo.toml b/Rust/Cargo.toml
@@ -1,7 +0,0 @@
-[package]
-name = "digital_sum"
-version = "0.1.0"
-authors = ["Gark Garcia <37553739+GarkGarcia@users.noreply.github.com>"]
-
-[dependencies]
-num_cpus = "1.0"-
\ No newline at end of file

diff --git a/Rust/main.rs b/Rust/main.rs
@@ -0,0 +1,112 @@
+// The following 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 integer.
+
+use std::{
+    env,
+    process,
+    thread,
+    sync::{Arc, mpsc::{self, Sender, Receiver}}
+};
+
+const SUCCESS: i32 = 0;
+const FAIL: i32 = 1;
+const INVALID_INPUT: i32 = 2;
+const DEFAULT_N_THREADS: usize = 1;
+
+fn main() {
+    let mut args = env::args();
+    args.next();
+
+    if let Some(max_str) = args.next() {
+        let n_threads = args.next()
+            .and_then(|s| s.trim().parse::<usize>().ok())
+            .unwrap_or(DEFAULT_N_THREADS);
+
+        if let Ok(max) =  max_str.trim().parse::<usize>() {
+            if countrexpl(max, n_threads) {
+                process::exit(FAIL);
+            } else {
+                process::exit(SUCCESS);
+            }
+        } else {
+            process::exit(INVALID_INPUT);
+        }
+    } else {
+        process::exit(INVALID_INPUT);
+    }
+}
+
+/// Distributes calculations across threads and collect the results
+fn countrexpl(max: usize, n_threads: usize) -> bool {
+    let sums_cache = Arc::new(get_sums(max));
+
+    if n_threads > 1 {
+        let (coutexpl_sender, coutexpl_reciever): (Sender<bool>, Receiver<bool>) = mpsc::channel();
+        let mut child_threads = Vec::with_capacity(n_threads);
+
+        for i in 0..n_threads {
+            let thread_countr_sd = coutexpl_sender.clone();
+            let thread_sums = sums_cache.clone();
+            let thread_range = (i..max).step_by(n_threads);
+
+            let child = thread::spawn(
+                move || thread_countr_sd.send(iter_countrexpl(thread_range, thread_sums, max)
+            ).expect(&format!("Thread n°{} was unable to sent a message trought the channel", i)));
+            
+            child_threads.push(child);
+            if let Ok(true) = coutexpl_reciever.recv() {
+                return true;
+            }
+        }
+
+        for child in child_threads {
+            child.join().expect("Child thread panicked");
+        }
+
+        false
+    } else {
+        iter_countrexpl(0..max, sums_cache, max)
+    }
+}
+
+/// Search for counterexamples among the items of a specif iterator.
+fn iter_countrexpl<I: IntoIterator<Item = usize>>(
+    iter: I,
+    sums_cache: Arc<Vec<isize>>,
+    max: usize
+) -> bool {
+    for a in iter {
+        for b in a..max {
+            let diff = sums_cache[a + b] - sums_cache[a] - sums_cache[b];
+            if diff % 9 != 0 {
+                return true;
+            }
+        }
+    }
+
+    false
+}
+
+fn sum_digits(n: usize) -> isize {
+    let mut sum = 0;
+    let mut part = n;
+
+    while part != 0 {
+        sum += part % 10;
+        part /= 10;
+    }
+
+    sum as isize
+}
+
+fn get_sums(max: usize) -> Vec<isize> {
+    let mut output = Vec::with_capacity(2 * max);
+
+    for n in 0..max * 2 {
+        output.push(sum_digits(n));
+    }
+
+    output
+}

diff --git a/Rust/src/main.rs b/Rust/src/main.rs
@@ -1,128 +0,0 @@
-// The following 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 integer.
-
-extern crate num_cpus;
-
-use std::{
-    env,
-    process,
-    thread,
-    sync::{Arc, Mutex, mpsc::{self, Sender, Receiver}},
-    collections::hash_map::{HashMap, Entry}
-};
-
-const SUCCESS: i32 = 0;
-const FAIL: i32 = 1;
-const INVALID_INPUT: i32 = 2;
-
-fn main() {
-    let args: Vec<String> = env::args().collect();
-
-    if args.len() > 1 {
-        let max_str = args[1].clone();
-
-        // Assign the correct number of threads to run the application with
-        // The default is the number of cores in the machine
-        let n_cores = num_cpus::get_physical();
-        let n_threads = if args.len() <= 2 { n_cores } else {
-            match args[2].trim().parse::<usize>() {
-                Ok(n_arg) => std::cmp::min(n_arg, n_cores),
-                Err(_) => n_cores
-            }
-        };
-
-        match max_str.trim().parse::<usize>() {
-            Ok(max) => if countrexpl(max, n_threads) {
-                process::exit(FAIL);
-            } else {
-                process::exit(SUCCESS);
-            }, 
-            Err(_) => process::exit(INVALID_INPUT)
-        }
-    } else {
-        process::exit(INVALID_INPUT);
-    }
-}
-
-/// Distributes calculations across threads and collect the results
-fn countrexpl(max: usize, n_threads: usize) -> bool {
-    let sums_cache = Arc::new(Mutex::new(HashMap::with_capacity(max)));
-
-    if n_threads > 1 {
-        let (coutexpl_sender, coutexpl_reciever): (Sender<bool>, Receiver<bool>) = mpsc::channel();
-        let mut child_threads = Vec::with_capacity(n_threads);
-
-        for i in 0..n_threads {
-            let thread_countr_sd = coutexpl_sender.clone();
-            let thread_sums = sums_cache.clone();
-
-            // By separating the interval [0..max] in subsections with the form [i + 0n, i + 1n, i + 2n, ...] we can ensure that every
-            // value will get tested on a single thread and that all threads will perform roughtly the same number of operations
-            let thread_range = (i..max).step_by(n_threads);
-
-            let child = thread::spawn(move || thread_countr_sd.send(iter_countrexpl(thread_range, thread_sums, max))
-                .expect(&format!("Thread n°{} was unable to sent a message trought the channel", i)));
-            
-            child_threads.push(child);
-            if let Ok(true) = coutexpl_reciever.recv() {
-                return true;
-            }
-        }
-
-        for child in child_threads {
-            child.join().expect("Child thread panicked");
-        }
-
-        false
-    } else {
-        iter_countrexpl(0..max, sums_cache, max)
-    }
-}
-
-/// Search for counterexamples among the items of a specif iterator.
-fn iter_countrexpl<I: IntoIterator<Item = usize>>(
-    iter: I,
-    sums_cache: Arc<Mutex<HashMap<usize, isize>>>,
-    max: usize
-) -> bool {
-    for a in iter {
-        for b in a..max {
-            let sum_a_b = lookup_or_insert(&sums_cache, a + b);
-            let sum_a   = lookup_or_insert(&sums_cache, a);
-            let sum_b   = lookup_or_insert(&sums_cache, b);
-            let diff    = sum_a_b - sum_a - sum_b;
-
-            if diff % 9 != 0 {
-                return true;
-            }
-        }
-    }
-
-    false
-}
-
-fn sum_digits(n: usize) -> isize {
-    let mut sum = 0;
-    let mut part = n;
-
-    while part != 0 {
-        sum += part % 10;
-        part /= 10;
-    }
-
-    sum as isize
-}
-
-fn lookup_or_insert(sums_cache: &Arc<Mutex<HashMap<usize, isize>>>, n: usize) -> isize {
-    if let Ok(ref mut sums_cache) = sums_cache.lock() { 
-        match (*sums_cache).entry(n) {
-            Entry::Vacant(entry) => *(entry.insert(sum_digits(n))),
-            Entry::Occupied(entry) => *(entry.get())
-        }
-    } else {
-        unimplemented!()
-    }
-}
-