# 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