                          Double Mersenne Number Factor Search Program “dmfs”
                                            Version 0.2


Welcome to dmfs, a multi-threaded program that searches for factors of Double Mersenne Numbers. These numbers have the form 
MM(n) = 2^(2^n - 1) - 1 where 2^n - 1 is a Mersenne prime. Factors of Double Mersenne numbers have the form D(k) = 2 * k * (2^n - 1) + 1.
For D(k) to divide MM(n), it is required that D(k) = 1 or 7 mod 8, which is equivalent to k = 0 or 1 mod 4.

dmfs searches for factors of Double Mersenne numbers within a list of search ranges. Each search range is specified by a single n and a range of k.
For each search range, dmfs first uses a sieve to eliminate trial divisors D(k) that are divisible by a small prime or have k != 0 or 1 mod 4.
The sieve currently supports up to the first 200 million primes, which results in 2.53% of the original k range surviving the sieve.
Sieve survivors are then tested to determine if they divide the Double Mersenne number. No PRP or primality test is done on the sieve survivors.

The 200 million small primes are stored in a file named "primes". If this file does not exist when dmfs is started, it will be created
which takes a few minutes. If the file exists and has a correct checksum it will be used, which takes less than a second.

For each search range, the range of k is divided into subranges called k groups, which are the units of work assigned to individual threads to search.

To efficiently use multiple processor cores within a system, dmfs has one master thread and multiple slave threads. Each thread is a Linux process.
The master thread reads the input file specifying the search ranges, launches the specified number of slave threads for each range, assigns k groups
to the slave threads to search, collects and prints results including factors found, and terminates all slave threads when the search range is complete. 
While all slave threads are busy searching k groups, the master thread periodically checks the slave threads for results then sleeps for 100ms
in order to make all cores available to the slave threads.

dmfs uses the GMP and GWNUM libraries and runs on x86-64 Linux systems. All testing has been done on Ubuntu. Currently there is no version of dmfs 
for Windows or macOS. dmfs is a CPU only program that does not use any GPUs installed in the system.

dmfs has been tested on MM(13) through MM(216091) and currently supports k < 2^50. It is primarily intended for MM(521) through MM(216091).
Below MM(521), other programs such as prime95 running ECM and mmff are far superior. Above MM(216091), a much deeper sieve is needed, 
so a combination of dmdsieve(cl) + prime95 is superior.


Installing and running dmfs
---------------------------

The download file dmfs_0.2.7z contains a readme.txt file (this file), the dmfs executable, program source files, and an example benchmark ranges input 
file (bench_8_core.in) and results output file (bench_8_core.out). These files can be extracted from the download file using: "7z e dmfs_0.2.7z".

dmfs reads the ranges file from stdin and writes results to stdout. dmfs is typically run as follows:

    dmfs <options> < ranges.in > results.out &

Executing dmfs in this manner enables it to run happily in the background, allowing the user to use the terminal window 
for other purposes or to log out completely.

In the ranges input file, lines starting with # and blank lines are ignored. Multiple search ranges can be specified, one range per line. 
Each range is specified using the following parameters (all must be present). Commas are allowed in the ki, kf and k_grp fields for readability.

    Column     Description
    --------   ---------------------------------------------------------------------------------------------------------------
    n          The exponent of the range. If 2^n - 1 is not a Mersenne prime, dmfs will report an error and skip the range.
    ki         The initial k of the range.
    kf         The final k of the range. ki through kf inclusive will be searched.
    k_grp      The range of k in a k group.
    n_primes   The number of small primes to use in the sieve. This is ignored unless the -mp command line option is used.
    n_threads  The number of slave threads to launch. Usually set to the number of processor cores in the system.

The results output file is written for each range start and done, and for each factor found. 
Factors in the results file can be displayed using "fgrep divides results.out".

dmfs command line options can be used to override program defaults and to enable additional output.
The full list of command line options with descriptions can be displayed using "dmfs -h":

Usage: dmfs [-a algorithm] [-d] [-h] [-mp] [-p] [-v] < ranges > results
    -a  Override the default algorithm which is selected based on N
        auto - Select the fastest algorithm based on N (default)
          pm - Use the GMP power/mod function. Best for small N. The default for n <= 3000.
          gw - Use the GWNUM square/mod function. Best for large N. The default for n > 3000.
         chk - Use both the GMP power/mod and GWNUM square/mod functions, and compare the results. For testing only.
    -d  Print debug information
    -h  Print this help and exit
   -mp  Manually set the number of sieve primes via the ranges file. Overrides auto selection. *** Required for now. ***
    -p  Report progress every 10% of each search range
    -v  Print more verbose output, including each K group start and stop

By default, dmfs uses the GMP library for MM(n) with n <= 2281 and the GWNUM library for n >= 3217. This threshold was determined
by running dmfs with a subset of the benchmark input file using both -a pm and -a gw.

Currently dmfs requires the number of sieve primes (n_primes) to be specified for each search range in the ranges.in file. 
The optimal value can be determined by running a small n/k range (runs for a few minutes of wall time) using various values of n_primes, 
and then selecting the n_primes that produces the highest value of "K range/CPU test sec". The bench_8_core.in file uses 
the optimal values of n_primes as determined on the author's computer.


Usage considerations
--------------------

For each k group (k_grp), the slave thread will first setup the sieve, then run the sieve while testing sieve survivors as they are found.
The time to setup the sieve is a function n and n_primes, and is mostly independent of the range of k. dmfs will have best performance
when k_grp is chosen such that the range of k (kf - ki + 1) = n_threads * k_grp, since each thread will do sieve setup only once for the range. 
However, if the system crashes or dmfs is killed, the range currently being searched will have to be restarted since, by default, 
progress within the range is only reported at range completion.

The -p option can be used to report percent progress through each search range. But since the slave threads are searching their k groups in parallel,
no single "k completed through K" is available to be printed until the search range is completed. So, on a system crash, the search range
would still need to be restarted.

If the user wishes to search a range that will take a long time and does not want to risk losing all progress on a system crash, a smaller
k_grp size can be selected such that (kf - ki + 1) = n_threads * n_grp * X, where X is an integer specifying the number of k groups that will be
assigned to each slave thread. Then by running dmfs with the -v option, dmfs will report ki and kf for each k group that completes. This will allow
the user to determine a "k completed through K" value after a system crash. The ranges input file can then be modified to start at this K value.

To stop dmfs gracefully after the set of k groups currently running is complete, create a file named "stop" ("touch stop") in the 
directory where dmfs is running. When the "stop" file is used in conjunction with a smaller k group size, this enables a search range to have X
different points at which the search can be gracefully stopped. The "stop" file will be automatically deleted the next time dmfs is started.


Building dmfs
-------------

The dmfs executable can be built from the source files using the following steps:

    1) Download and install the GMP library by following their instructions. Make sure to run "make install".
    2) Download the Software Source Code (zip file) from the bottom of the GIMPS download page into an mprime_root_directory.
       Unzip the file and build the GWNUM library by going to the gwnum directory and following the instructions in the readme.txt file.
    3) In the dmfs directory, run "link_gwnum <path_to_mprime_root_directory> to create links to the needed gwnum files.
    4) In the dmfs directory, run "make".

