# a-conjecture-of-mine

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

# README.adoc (4503B)

1 = A Conjecture of Mine 2 3 An exercise on _polyglossy_. The same problem solved on multiple languages. 4 5 == The Problem - Mathematicians' Version 6 7 Let latexmath:[S : \mathbb{N} \rightarrow \mathbb{N}] be the sum of the 8 digits of a natural number. Then 9 latexmath:[S(n + m) \equiv S(n) + S(m) \; (\textrm{mod} \; 9)] for all 10 natural numbers latexmath:[n] and latexmath:[m]. 11 12 This conjecture can be generalized for any _positional number system_. 13 14 == The Problem - Programmers' Verison 15 16 Let `S(n: uint) -> uint` be the sum of the digits of `n` in 17 https://en.wikipedia.org/wiki/Decimal[_base 10_]. Then, for all `a` and `b` 18 of type `uint`, `S(a + b) - S(a) - S(b) % 9 == 0`. 19 20 == Performance 21 22 The conjecture was 23 https://en.wikipedia.org/wiki/Proof_by_exhaustion[proved by exhaustion] for 24 the interval latexmath:[10^5] 25 in multiple language implementations. The performance of each language was then 26 avaliated as the following _(*)_: 27 28 [%header,format=csv] 29 |=== 30 Language,Milliseconds,Processes 31 include::stats.csv[] 32 |=== 33 34 _(*) not all implementations were benchmarked_ 35 36 == Contributing 37 38 Contributions are welcomed! If you want to create a solution in a different 39 language or improve the work on an existing implementation, feel free to help 40 out. 41 42 However, to ensure we are _comparing apples to apples_ a similar algorithm 43 should be used on all implementations. 44 45 === The Algorithm 46 47 The program should test the conjecture **for all pairs `(a, b)` where 48 `0 <= a <= MAX` and `0 <= b <= a`**, as this is sufficient to proof the 49 conjecture **for all pairs `(a, b)` between `0` and `MAX`**. The value of `MAX` 50 should be provided in the first command-line argument. 51 52 The following algorithm should be used: 53 54 ---- 55 for a between 0 and MAX: 56 for b between 0 and a: 57 check if the conjecture holds for the pair (a, b) 58 59 if it fails: 60 exit the process with exit code 1 61 62 exit the process with exit code 0 63 ---- 64 65 Alternativelly, one could iterate `b` between `a` and `MAX`. 66 67 === Concurency 68 69 The use of concurrency is encoraged for implementations on languages that 70 provide good _standard_ support for it. In the case concurrency is used, an 71 additional, optional parameter `NPROCESSES` should be passed to the application 72 in the seccond command-line argument. 73 74 The default value of `NPROCESSES` should be `1`. The algorithm should then be 75 addapted to the following: 76 77 ---- 78 for i between 0 and NPROCESSES: 79 lauch a process running counterexample(start=i) 80 81 for each opened process: 82 wait for the process to signal it's results 83 84 if the process signals a counterexample was found: 85 exit the main process with exit code 1 86 87 exit the main process with exit code 0 88 ---- 89 90 The algorith for the `counterexample` routine should be the following: 91 92 ---- 93 for a between 0 and MAX by steps of NPROCESSES: 94 for b between 0 and a: 95 check if the conjecture holds for the pair (a, b) 96 97 if it fails: 98 signal to the main process that a counterexample was found 99 100 signal to the main process that no counterexample was found 101 ---- 102 103 This scheme ensures computations are envenlly distributed across processes. 104 Note that the routine should only signal wheter or not a counterexample was 105 found. 106 107 === Caching 108 109 When checking if the conjecture holds for the pair `(a, b)`, the program will 110 need to calculate the sum of the digits of `a`, `b` and `a + b`. To avoid 111 calculating those values multiple times, the sum of the digits of `n` should 112 be cached, for all `n` between `0` and `2 * MAX + 1`. 113 114 There are two allowed strategies for caching this values. 115 116 The first one involves storing the sum of the digits of `n` in a vector 117 (indexed by `n`) before starting the test. An immutable reference to this 118 vector could then be distributed across processes as necessary. 119 120 The second one involves storing the results in a map and calculating them as 121 they are need in the following matter: 122 123 ---- 124 if n is a key in the map: 125 return map[n] 126 else: 127 calculate the sum of the digits of n 128 insert the pair (n, sum of the digits of n) in the map 129 return the sum of the digits of n 130 ---- 131 132 A mutable reference to the map could then be distributed across processes as 133 necessary. 134 135 The seccond strategy is recommend for concurent implementations, while the 136 first one is more suitable for implementations that use a single process. 137