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