a-conjecture-of-mine

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

git clone: git://git.pablopie.xyz/a-conjecture-of-mine
Log
Files
Refs

Commit: c48325f8f47c3f02cb5da919e42394ed63332911
Parent: 7fc0c8aee453c1ac1f07b0170a42a43d2b559dab
Author: Pablo Escobar Gaviria <gark.garcia@protonmail.com>
Date: Wed, 22 Jan 2020 12:26:55 -0200

Finished describing the general algorithm in `README.md`.

Diffstat

1 file changed, 28 insertions, 1 deletion

Status	File Name	N° Changes	Insertions	Deletions
Modified	README.md	29	28	1

diff --git a/README.md b/README.md
@@ -112,5 +112,32 @@ found.
 
 ### Caching
 
-TODO
+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.