# a-conjecture-of-mine

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

commit99b065bd7dba791b2f25e9b24ef538549e8b6e2cparent4caf6d369930d63947b45544ca9a9bb090f5fd9aAuthor:Pablo Emilio Escobar Gaviria <pablo-escobar@riseup.net>Date:Tue, 14 Apr 2020 08:08:30 -0300 Updated the READMEDiffstat:

M | C/main.c | | | 2 | +- |

M | Elixir/main.ex | | | 6 | +++--- |

M | Extra/x86/PROGRAM.ASM | | | 26 | +++++++++++++------------- |

M | Haskell/Main.hs | | | 6 | +++--- |

M | OCaml/main.ml | | | 5 | ++--- |

A | README.adoc | | | 146 | +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ |

D | README.md | | | 142 | ------------------------------------------------------------------------------- |

M | Rust/main.rs | | | 11 | +++++------ |

M | script.js | | | 2 | +- |

M | script.pl | | | 4 | ++-- |

M | script.py | | | 1 | - |

M | script.rb | | | 6 | ++---- |

diff --git a/C/main.c b/C/main.c@@ -81,7 +81,7 @@ int main(int argc, char *argv[]) // Create the sums cache sums_cache = malloc(sizeof(int) * (2 * max + 1)); - for (int i = 0; i <= sums_c; i++) + for (int i = 0; i <= 2 * max + 1; i++) sums_cache[i] = sum_digits(i);diff --git a/Elixir/main.ex b/Elixir/main.ex@@ -13,10 +13,10 @@ defmodule Conjecture do # Spawn a new process for each starting index from 0 to `max` f = fn i -> - spawn fn -> counterexpl i, max, n_processes, parent_id end - end - Enum.map 0..(n_processes - 1), f + spawn fn -> counterexpl i, max, n_processes, parent_id end + end + Enum.map 0..(n_processes - 1), f listen n_processes end enddiff --git a/Extra/x86/PROGRAM.ASM b/Extra/x86/PROGRAM.ASM@@ -23,7 +23,7 @@ cache_sums: mov cx, 2 mul cx ; ax = max * 2 -cache_sums_loop: +cache_sums.loop: call sum_digits mov [si], bx @@ -31,7 +31,7 @@ cache_sums_loop: dec ax cmp ax, 0 - ja cache_sums_loop ; while ax > 0, keep looping + ja cache_sums.loop ; while ax > 0, keep looping pop ax ; Restore the value of max to ax ret @@ -40,12 +40,12 @@ cache_sums_loop: ; At the start of this routine ax holds the value of max counterexpl: mov cx, 9 ; Set the devident to 9 -counterexpl_loop: +counterexpl.loop: call iter dec ax ; a -= 1 cmp ax, 0 ; if a > 0, keep looping - ja counterexpl_loop + ja counterexpl.loop call ok ret @@ -54,12 +54,12 @@ counterexpl_loop: ; At the start of this routine ax holds the value of a iter: mov bx, ax -iter_loop: +iter.loop: call test_pair dec bx cmp bx, 0 - jae iter_loop + jae iter.loop ret ; At the start of this routine ax holds the value of a @@ -116,7 +116,7 @@ sum_digits: mov cx, 10 ; Store the devident in cx mov bx, 0 ; Clear the register where the result will be stored -sum_loop: +sum_digits.loop: mov dx, 0 ; Clear the rest of the division div cx ; Divide ax by cx @@ -124,7 +124,7 @@ sum_loop: ; Loop until ax equals 0 cmp ax, 0 - ja sum_loop + ja sum_digits.loop pop ax ret @@ -140,16 +140,16 @@ read_uint: ;mov si, ds mov si, 5eh -read_loop: +read_uint.loop: ; Read a character from the command-line tail mov bh, 0 mov bl, [si] ; Jump out of the loop at the end of the first arg cmp bl, ' ' - jmp read_uint_end + jmp read_uint.end cmp bl, 0dh - jmp read_uint_end + jmp read_uint.end ; Check if it's a numeric character cmp bl, 30h @@ -166,9 +166,9 @@ read_loop: ; Increment the pointer to the argument string and keep looping inc si - jmp read_loop + jmp read_uint.loop -read_uint_end: +read_uint.end: pop si retdiff --git a/Haskell/Main.hs b/Haskell/Main.hs@@ -32,9 +32,8 @@ sumDigits = sumDigitsTail 0 | n == 0 = acc | otherwise = sumDigitsTail (acc + (n `mod` 10)) (n `div` 10) --- Returns `Just updated` if the if the conjecture holds for pair, where --- `updated` is an updated versions of the sums cache provided by `sums`. --- Otherwise returns `Nothing`. +-- Returns `True` if the if the conjecture holds for pair. +-- Otherwise returns `False`. test' :: Vector Int -> (Int, Int) -> Bool test' sums (a, b) = diff `mod` 9 == 0 where diff = sums ! (a + b) - sums ! a - sums ! b @@ -52,3 +51,4 @@ counterexempl max = exitInvalidInput :: IO Int exitInvalidInput = exitWith $ ExitFailure 2 +diff --git a/OCaml/main.ml b/OCaml/main.ml@@ -26,9 +26,8 @@ let test (a: int) (b: int) (sums_cache: int array) : bool = let rec listen (c: bool Event.channel) (n: int) : unit = match n with | 0 -> () - | _ -> - if Event.sync (Event.receive c) then exit failure - else listen c (n - 1) + | _ when Event.sync (Event.receive c) -> exit failure + | _ -> listen c (n - 1) let counterexempl (max: int) (n_threads: int) : unit = let sums_cache = get_sums maxdiff --git a/README.adoc b/README.adoc@@ -0,0 +1,146 @@ += A Conjecture of Mine + +An exercise on _polyglossy_. The same problem solved on multiple languages. + +== The Problem - Mathematicians Version + +Let latexmath:[$S : \mathbb{N} \rightarrow \mathbb{N}$] +be the sum of the digits of a positive integer in a +https://en.wikipedia.org/wiki/Positional_notation[_base 10 positional number system_]. +We have: + +[latexmath] +++++ +\forall a, b \in \mathbb{N}, S_{a + b} \equiv S_a + S_b \;\(\textup{mod}\; 9 \) +++++ + +This conjecture can be generalized for any _positional number system_. +Check out `proof.pdf` for more information. + +== The Problem - Programmers Verison + +Let `S(n: uint) -> uint` be the sum of the digits of `n` in +_[base 10](https://en.wikipedia.org/wiki/Decimal)_. Then, for all `a` and `b` +of type `uint`, `S(a + b) - S(a) - S(b) % 9 == 0`. + +== Performance + +The conjecture was +https://en.wikipedia.org/wiki/Proof_by_exhaustion[proved by exhaustion] for +the interval latexmath:[$10^5$] +in multiple language implementations. The performance of each language was then +avaliated as the following _(*)_: + +|Language |Milliseconds|Processes| +|--------------|------------|---------| +|**C** |15.441 |4 | +|**Rust** |42.508 |4 | +|**Kotlin** |12480 |1 | +|**OCaml** |30448 |1 | +|**Go** |70459 |4 | +|**Haskell** |121000 |1 | + +_(*) not all implementations were benchmarked_ + +== Contributing + +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, to ensure we are _comparing apples to apples_ a similar algorithm +should be used on all implementations. + +## The Algorithm + +The program should test the conjecture **for all pairs `(a, b)` where +`0 <= a <= MAX` and `0 <= b <= a`**, as this is sufficient to proof the +conjecture **for all pairs `(a, b)` between `0` and `MAX`**. The value of `MAX` +should be provided in the first command-line argument. + +The following algorithm should be used: + +---- +for a between 0 and MAX: + for b between 0 and a: + check if the conjecture holds for the pair (a, b) + + if it fails: + exit the process with exit code 1 + +exit the process with exit code 0 +---- + +Alternativelly, one could iterate `b` between `a` and `MAX`. + +### Concurency + +The use of concurrency is encoraged for implementations on languages that +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: + +---- +for i between 0 and NPROCESSES: + lauch a process running counterexample(start=i) + +for each opened process: + wait for the process to signal it's results + + if the process signals a counterexample was found: + exit the main process with exit code 1 + +exit the main process with exit code 0 +---- + +The algorith for the `counterexample` routine should be the following: + +---- +for a between 0 and MAX by steps of NPROCESSES: + for b between 0 and a: + check if the conjecture holds for the pair (a, b) + + if it fails: + signal to the main process that a counterexample was found + +signal to the main process that no counterexample was found +---- + +This scheme ensures computations are envenlly distributed across processes. +Note that the routine should only signal wheter or not a counterexample was +found. + +### Caching + +When checking if the conjecture holds for the pair `(a, b)`, the program will +need to calculate the sum of the digits of `a`, `b` and `a + b`. To avoid +calculating those values multiple times, the sum of the digits of `n` should +be cached, for all `n` between `0` and `2 * MAX + 1`. + +There are two allowed strategies for caching this values. + +The first one involves storing the sum of the digits of `n` in a vector +(indexed by `n`) before starting the test. An immutable reference to this +vector could then be distributed across processes as necessary. + +The second one involves storing the results in a map and calculating them as +they are need in the following matter: + +---- +if n is a key in the map: + return map[n] +else: + calculate the sum of the digits of n + insert the pair (n, sum of the digits of n) in the map + return the sum of the digits of n +---- + +A mutable reference to the map could then be distributed across processes as +necessary. + +The seccond strategy is recommend for concurent implementations, while the +first one is more suitable for implementations that use a single process. +diff --git a/README.md b/README.md@@ -1,142 +0,0 @@ -# A Conjecture of Mine -An exercise on _polyglossy_. The same problem solved on multiple languages. - -# The Problem - Mathematicians Version -Let -<img src="https://latex.codecogs.com/svg.latex?S:&space;\mathbb{N}\rightarrow&space;\mathbb{N}"/> -be the sum of the digits of a positive integer in a -_[base 10 positional number system](https://en.wikipedia.org/wiki/Positional_notation)_. -We have: - -<img src="https://latex.codecogs.com/svg.latex?\forall&space;a,&space;b&space;\in&space;\mathbb{N},&space;S_{a&space;+&space;b}&space;\equiv&space;S_a&space;+&space;S_b&space;\;\(\textup{mod}\;&space;9&space;\)"/> - -This conjecture can be generalized for any _positional number system_. -Check out `proof.pdf` for more information. - -# The Problem - Programmers Verison - -Let `S(n: uint) -> uint` be the sum of the digits of `n` in -_[base 10](https://en.wikipedia.org/wiki/Decimal)_. Then, for all `a` and `b` -of type `uint`, `S(a + b) - S(a) - S(b) % 9 == 0`. - -# Performance - -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^5]"/> -in multiple language implementations. The performance of each language was then -avaliated as the following _(*)_: - -|Language |Milliseconds|Processes| -|--------------|------------|---------| -|**C** |15.441 |4 | -|**Rust** |42.508 |4 | -|**Kotlin** |12480 |1 | -|**OCaml** |30448 |1 | -|**Go** |70459 |4 | -|**Haskell** |121000 |1 | - -_* not all implementations were benchmarked_ - -# Contributing - -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, to ensure we are _comparing apples to apples_ a similar algorithm -should be used on all implementations. - -## The Algorithm - -The program should test the conjecture **for all pairs `(a, b)` where -`0 <= a <= MAX` and `0 <= b <= a`**, as this is sufficient to proof the -conjecture **for all pairs `(a, b)` between `0` and `MAX`**. The value of `MAX` -should be provided in the first command-line argument. - -The following algorithm should be used: - -``` -for a between 0 and MAX: - for b between 0 and a: - check if the conjecture holds for the pair (a, b) - - if it fails: - exit the process with exit code 1 - -exit the process with exit code 0 -``` - -Alternativelly, one could iterate `b` between `a` and `MAX`. - -### Concurency - -The use of concurrency is encoraged for implementations on languages that -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: - -``` -for i between 0 and NPROCESSES: - lauch a process running counterexample(start=i) - -for each opened process: - wait for the process to signal it's results - - if the process signals a counterexample was found: - exit the main process with exit code 1 - -exit the main process with exit code 0 -``` - -The algorith for the `counterexample` routine should be the following: - -``` -for a between 0 and MAX by steps of NPROCESSES: - for b between 0 and a: - check if the conjecture holds for the pair (a, b) - - if it fails: - signal to the main process that a counterexample was found - -signal to the main process that no counterexample was found -``` - -This scheme ensures computations are envenlly distributed across processes. -Note that the routine should only signal wheter or not a counterexample was -found. - -### Caching - -When checking if the conjecture holds for the pair `(a, b)`, the program will -need to calculate the sum of the digits of `a`, `b` and `a + b`. To avoid -calculating those values multiple times, the sum of the digits of `n` should -be cached, for all `n` between `0` and `2 * MAX + 1`. - -There are two allowed strategies for caching this values. - -The first one involves storing the sum of the digits of `n` in a vector -(indexed by `n`) before starting the test. An immutable reference to this -vector could then be distributed across processes as necessary. - -The second one involves storing the results in a map and calculating them as -they are need in the following matter: - -``` -if n is a key in the map: - return map[n] -else: - calculate the sum of the digits of n - insert the pair (n, sum of the digits of n) in the map - return the sum of the digits of n -``` - -A mutable reference to the map could then be distributed across processes as -necessary. - -The seccond strategy is recommend for concurent implementations, while the -first one is more suitable for implementations that use a single process. -diff --git a/Rust/main.rs b/Rust/main.rs@@ -52,7 +52,9 @@ fn counterexempl(max: usize, n_threads: usize) -> bool { let child = thread::spawn( 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))); + ).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() { @@ -77,16 +79,12 @@ fn counterexempl_range( max: usize ) -> bool { let mut a = 0usize; - let mut b; while a <= max { - b = 0; - while b <= a { + for b in a..max { if (sums_cache[a + b] - sums_cache[a] - sums_cache[b]) % 9 != 0 { return true; } - - b += 1; } a += step; @@ -116,3 +114,4 @@ fn get_sums(max: usize) -> Vec<isize> { output } +diff --git a/script.js b/script.js@@ -15,7 +15,7 @@ function sumDigits(n) { } function getSums(max) { - const output = [], maxRange = 2 * (max + 1); + const output = [], maxRange = 2 * max + 1; for (let i = 0; i <= maxRange; i++) output.push(sumDigits(i));diff --git a/script.pl b/script.pl@@ -25,6 +25,6 @@ test_pair(A, B) :- iter(A) :- forall(between(0, A, B), test_pair(A, B)). -conjecture(Mod) :- - forall(between(0, Mod, A), iter(A)). +conjecture(Max) :- + forall(between(0, Max, A), iter(A)).diff --git a/script.py b/script.py@@ -27,4 +27,3 @@ def counterexempl(max: int) -> bool: return True return False -diff --git a/script.rb b/script.rb@@ -13,7 +13,7 @@ def sum_digits(i) part = d end - return sum + sum end def get_sums(max) @@ -22,8 +22,6 @@ def get_sums(max) for i in 0..(2 * max + 1) output << sum_digits(i) end - - return output end def counterexempl(max) @@ -39,6 +37,6 @@ def counterexempl(max) end end - return false + false end