Calculating M(n)

The Parallel Run

Among the many files here, only some of them directly contributed to the run that found M(2^30). See test/PSegNFree.cpp. It leverages alg/a5Free.h, calculating delta(n) working modulo 60. In addition, it uses util/freeFunc.h to help initialize the data structures used working modulo 60.

Arbitrary Modulus

Each algorithm that works under a modulus uses a few constant arrays to look up how to traverse through the multiplication table. Take for example, determining table values remainder 0 modulo 6. For rows that are a multiple of 6, every cell must be checked. In this case, the "row step" is 1. For rows that are 1 more than a multiple of 6, there is a multiple of 6 every 6 colums, so the "row step" is 6. When examining table values remainder 1 modulo 6, some columns will never contain such values. These rows are skipped, so the "column step" might be 2. The row and column steps can change dramatically where you are in the table, so all of these steps are stored in large arrays. A look up after every product is calculated to determine which product to calculate next.

The file that generates these steps is step_generator/step_gen.cpp. The steps are written to a file and can then be inserted into the program as a constant multidimensional array. Alternatively, the aNFree.h algorithm generates these step arrays in the heap at the start of runtime.

Summary of Files

• alg Algorithms used to calculate delta(n).
  • a0Free.h Calculates delta(n) in the most naive way possible.
  • a1Free.h Calculates delta(n) by skipping the first row of the table.
  • a2Free.h Calculates delta(n) working modulo 2.
  • a3Free.h Calculates delta(n) working modulo 6.
  • a4Free.h Calculates delta(n) working modulo 12.
  • a5Free.h Calculates delta(n) working modulo 60.
  • aNFree.h Calculates delta(n) for a variable modulus, that is, the least common multiple of integers 1 to N. First it creates a series of vectors that stores "step" data, that is, how to traverse across the multiplication table under modulo N.
  • aModN.h BROKEN. Calculates delta(n) under ANY modulus.
  • aFast.h BAD. Calculates particular delta(n) using constant time evaluation rules. Supports n=p*k, for prime p and k <= 16. Done using a series of switch statements.
  • aHash.h Calculates particular delta(n) using constant time evaluation rules. Supports n=p*k, for prime p. Reads from the constants folder to create a series of hashmaps to evaluate the rules. Those files were generated by another program.
  • aShift.h Implementation of Algorithm 3. Calculates families of delta(n) values. For a multiplier m, it calculates delta(mp) for prime p.
  • aFill.h Implementation of Algorithm 4.
  • nine_rules.h and three_up_fast_rules.h are switch statements used in aFast.h
• util Functions and structs used across many algorithms.
  • Sieve.h Sieve of Eratosthenes implementation.
  • Factoration.h Struct that represents the factorization of a given number.
  • fastFact.h Segmented sieve that creates factorization structs across an interval.
  • freeFunc.h Functions used in the initialization of aXFree.h algorithms.
  • shiftFunc.h Functions used in aShift.h and aFill.h.
• test Performs the actual m(n) calculation leveraging a variety of different algorithms described above. For example, tFast12Free.cpp uses the aFast.h, a1Free.h, and a2Free.h files.
  • PSegNFree.cpp Performed the M(n) calculation in parallel to get M(2^30).
• sh Bash scripts that validate the test the files in test to ensure algorithms provide the correct delta(n) and M(n) calculations.
• constants Data used to initialize the hashmap in aHash.h
• scripts Some additional scripts used when parsing M(n) values.
• step_generator Constructs files with all the different step values need to run aNFree.h. Used when creating a new aXFree.h algorithm. For example, the first lines of a5Free.h were generated by this program.

Executables are compliled to bin/ and output from sh scripts are written to data/.