At this moment, the process of validating huge statespaces goes like this, in 2 phases:
- Scanning the semi-arcs: the heavy and parallel phase can distribute ranges of arcs to scan, among whatever processing units are available. Each range will then create a log file, that contains the length of each consecutive arc, as well as the coordinates of crossing.
- The post-processing phase takes all the log files and reconstructs the orbit(s) by concatenating arcs. This is where we get to know if the corresponding statespace is "maximal" or ideal.
The latter part is the subject of this log: once we get all those log files (I estimate 50GB for w32), what can be done ?
The first and easiest process that comes to mind is to compute the sum of the length of all the semi-arcs. This sum should have a certain value that we have already validated. This sum however is not a fail-proof method because we have seen many cases (such as w6 and its 6 orbits) where there are no small orbits isolated in a sea of huge orbits (such as w12 or w14).
Summing all the arcs should be easy, using a script that computes the sum for each log file, then summing all these sums. The filename itself could even contain the sum, computed when the scanner writes the results/log to disk.
To get a taste of what might happen, I tested with the smallest widths:
$ for i in 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 ; do gcc -Wall -Os -DWIDTH=$i scan_1x_02.c -o scan ./scan done Width=2 Total= 8 vs 8 (missing 0) Width=3 Total= 34 vs 34 (missing 0) Width=4 Total= 134 vs 134 (missing 0) Width=5 Total= 524 vs 526 (missing 2) Width=6 Total= 2078 vs 2078 (missing 0) <=== hey ! Width=7 Total= 8156 vs 8254 (missing 98) Width=8 Total= 19204 vs 32894 (missing 13690) Width=9 Total= 130659 vs 131326 (missing 667) Width=10 Total= 524798 vs 524798 (missing 0) Width=11 Total= 2095073 vs 2098174 (missing 3101) Width=12 Total= 8390625 vs 8390654 (missing 29) Width=13 Total= 33558524 vs 33558526 (missing 2) Width=14 Total= 134225868 vs 134225918 (missing 50) Width=15 Total= 536775077 vs 536887294 (missing 112217) Width=16 Total= 2147516414 vs 2147516414 (missing 0) Width=17 Total= 8589998504 vs 8590000126 (missing 1622) Width=18 Total= 34359868344 vs 34359869438 (missing 1094)
Except for w6, all the widths with a mismatched sum have more than one pair of orbits. This means that the sum is not the definitive answer but it is definitely part of it: if the sum doesn't match the expected total, this means that there are orbits that don't cross the Y=0 line and the corresponding statespace is not maximal.
The second part is required, since the first part is only a first check. It is less easy to implement, particularly when the logs exceed the size of the RAM. Partial lookups become necessary, over multiple passes.
Thanks to YouTube's suggestions for remining me this nice video:
See you in the next log.