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