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: f00a25dbba8a5949c25ded19c8df75f874e91076
Parent: c48325f8f47c3f02cb5da919e42394ed63332911
Author: Pablo Escobar Gaviria <gark.garcia@protonmail.com>
Date: Sat, 1 Feb 2020 22:43:28 -0200

Updated benchmarking information.

Diffstat

7 files changed, 83 insertions, 28 deletions

Status	File Name	N° Changes	Insertions	Deletions
Added	.stack-work/install/x86_64-linux-nopie/ghc-8.0.2/8.0.2/pkgdb/package.cache	0	0	0
Modified	Idris/Main.idr	3	1	2
Added	OCaml/main.ml	53	53	0
Modified	README.md	25	12	13
Modified	Rust/main.rs	22	12	10
Modified	Wasm/main.wat	2	1	1
Modified	script.rkt	6	4	2

diff --git a/.stack-work/install/x86_64-linux-nopie/ghc-8.0.2/8.0.2/pkgdb/package.cache b/.stack-work/install/x86_64-linux-nopie/ghc-8.0.2/8.0.2/pkgdb/package.cache
Binary files differ.

diff --git a/Idris/Main.idr b/Idris/Main.idr
@@ -6,13 +6,12 @@
 module Main
 
 import System
-import Data.Map
 
 main : IO Int
 main = do
     args <- getArgs
         
-    case readDeci <$> head' args of
+    case readDec <$> head' args of
       Just [(max, "")] =>
         if counter' max then exitFailure else exitSuccess
       _ => exitInvalidInput

diff --git a/OCaml/main.ml b/OCaml/main.ml
@@ -0,0 +1,53 @@
+(* 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. *)
+
+let failure: int = 1;;
+let invalid_input: int = 2;;
+
+(** Returns the sum of the digits of `n`, where `n` is a positive integer. *) 
+let sum_digits (n: int) : int =
+    let rec sum_digits_tail n acc =
+        match n with
+        | 0 -> acc
+        | _ -> sum_digits_tail (n / 10) (acc + n mod 10)
+    in 
+        sum_digits_tail n 0
+;;
+
+(** Precompute the values of `sum_digits`.*)
+let get_sums (max: int) : int array =
+    Array.init (2 * max + 1) sum_digits
+;;
+
+let test (a: int) (b: int) (sums_cache: int array) : bool =
+    let sum_digits n = Array.get sums_cache n in
+    0 = (sum_digits (a + b) - sum_digits a - sum_digits b) mod 9
+;;
+
+(* TODO: Use concurency. *)
+let counterexempl (max: int) : unit =
+    let sums_cache = get_sums max in
+    for a = 0 to max do 
+        for b = 0 to a do
+            if test a b sums_cache then () else exit failure
+        done
+    done
+;;
+
+let main () =
+    if Array.length Sys.argv > 1 then
+        let max_str = Sys.argv.(1) in
+
+        match int_of_string_opt max_str with
+        | Some max when max > 0 -> counterexempl max 
+        | _ -> exit invalid_input
+    else
+        exit invalid_input
+;;
+
+let () = 
+    main ()
+

diff --git a/README.md b/README.md
@@ -23,20 +23,18 @@ of type `uint`, `S(a + b) - ( S(a) + S(b) ) % 9 == 0`.
 
 The conjecture was 
 [proved by exhaustion](https://en.wikipedia.org/wiki/Proof_by_exhaustion) for 
-the interval <img src="https://latex.codecogs.com/svg.latex?[0,&space;10^4]"/> 
+the interval <img src="https://latex.codecogs.com/svg.latex?[0,&space;10^5]"/> 
 in multiple language implementations. The performance of each language was then 
 avaliated as the following _(*)_:
 
 |Language      |Milliseconds|
 |--------------|------------|
-|**Rust**      |103         |
-|**C**         |113         | 
-|**Kotlin**    |137         |
-|**Go**        |155         |
-|**JavaScript**|656         |
-|**Ruby**      |9850        |
-|**Python**    |16032       |
-|**Haskell**   |28365       |
+|**Go**        |4.1073      |
+|**C**         |15.441      | 
+|**Rust**      |42.508      |
+|**Kotlin**    |12480       |
+|**OCaml**     |30448       |
+|**Haskell**   |121000      |
 
 _* out of date_
 
@@ -46,7 +44,8 @@ Contributions are welcomed! If you want to create a solution in a different
 language or improve the work on an existing implementation, feel free to help 
 out.
 
-However, there are some guidelines. 
+However, to ensure we are _comparing apples to apples_ a similar algorithm 
+should be used on all implementations. 
 
 ## The Algorithm
 
@@ -73,9 +72,9 @@ Alternativelly, one could iterate `b` between `a` and `MAX`.
 ### Concurency
 
 The use of concurrency is encoraged for implementations on languages that 
-provide good support for it. In the case concurrency is used, an additional, 
-optional parameter `NPROCESSES` should be passed to the application in the 
-seccond command-line argument.
+provide good _standard_ support for it. In the case concurrency is used, an 
+additional, optional parameter `NPROCESSES` should be passed to the application 
+in the seccond command-line argument.
 
 The default value of `NPROCESSES` should be `1`. The algorithm should then be 
 addapted to the following:

diff --git a/Rust/main.rs b/Rust/main.rs
@@ -25,7 +25,7 @@ fn main() {
             .unwrap_or(DEFAULT_N_THREADS);
 
         if let Ok(max) =  max_str.trim().parse::<usize>() {
-            if countrexpl(max, n_threads) {
+            if counterexempl(max, n_threads) {
                 process::exit(FAIL);
             } else {
                 process::exit(SUCCESS);
@@ -39,7 +39,7 @@ fn main() {
 }
 
 /// Distributes calculations across threads and collect the results
-fn countrexpl(max: usize, n_threads: usize) -> bool {
+fn counterexempl(max: usize, n_threads: usize) -> bool {
     let sums_cache = Arc::new(get_sums(max));
 
     if n_threads > 1 {
@@ -49,10 +49,9 @@ fn countrexpl(max: usize, n_threads: usize) -> bool {
         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)
+                move || thread_countr_sd.send(counterexempl_range(thread_sums, max, n_threads)
             ).expect(&format!("Thread n°{} was unable to sent a message trought the channel", i)));
             
             child_threads.push(child);
@@ -67,23 +66,26 @@ fn countrexpl(max: usize, n_threads: usize) -> bool {
 
         false
     } else {
-        iter_countrexpl(0..max, sums_cache, max)
+        counterexempl_range(sums_cache, max, 1)
     }
 }
 
 /// Search for counterexamples among the items of a specif iterator.
-fn iter_countrexpl<I: IntoIterator<Item = usize>>(
-    iter: I,
+fn counterexempl_range(
     sums_cache: Arc<Vec<isize>>,
+    step: usize,
     max: usize
 ) -> bool {
-    for a in iter {
+    let mut a = 0usize;
+
+    while a <= max {
         for b in a..max {
-            let diff = sums_cache[a + b] - sums_cache[a] - sums_cache[b];
-            if diff % 9 != 0 {
+            if (sums_cache[a + b] - sums_cache[a] - sums_cache[b]) % 9 != 0 {
                 return true;
             }
         }
+
+        a += step;
     }
 
     false

diff --git a/Wasm/main.wat b/Wasm/main.wat
@@ -80,7 +80,7 @@
         (local.get $sum) ;; return sum
     )
 
-    ;; Checks if (sum_digits(a + b) - (sum_digits(a) + sum_digits(b))) % 9 != 0
+    ;; Checks if (sum_digits(a + b) - sum_digits(a) - sum_digits(b)) % 9 != 0
     (func $test (export "test") (param $a i32) (param $b i32) (result i32) 
           (i32.ne
             (i32.const 0)

diff --git a/script.rkt b/script.rkt
@@ -7,11 +7,13 @@
 
 (provide counterexempl)
 
+;; Returns `#t` if a counterexemple was found between `0` and `max`.
+;; Otherwise returns `#f`.
 (define (counterexempl max)
     (let ([sums-cache (get-sums max)])
          (not (stream-fold (lambda (acc a) (and acc (iter a sums-cache)))
-                     #t
-                     (in-range max)))))
+                           #t
+                           (in-range max)))))
 
 (define (iter a sums-cache)
     (stream-fold (lambda (acc b) (and acc (test a b sums-cache)))