Ernst's Mfactor program

[ATH]

As I wrote earlier all these factors except for M(74207281²) and M(82589933²) I posted earlier, were originally found by my own GMP code, I just posted them now for more debug examples, which apparently was a good idea

[kriesel]

Program output for help is

$ ./mfactor.exe -h
INFO: testing qfloat routines...
CPU Family = x86_64, OS = Linux, 64-bit Version, compiled with Gnu C [or other compatible], Version 8.2.0.
INFO: CPU supports SSE2 instruction set, but using scalar floating-point build.
INFO: Using inline-macro form of MUL_LOHI64.
INFO: MLUCAS_PATH is set to ""
Setting DAT_BITS = 10, PAD_BITS = 2
INFO: testing IMUL routines...
 Mfactor command line options ...
 <CR>        Default mode: prompts for manual keyboard entry

 -h          Prints this help file and exits

 -m {num}    Trial-factor the Mersenne number M(num) = 2^num - 1.

 -mm {num}   Trial-factor the double-Mersenne number M(M(num)) = 2^(2^num) - 1.

 -f {num}    Trial-factor the Fermat number F(num) = 2^(2^num) + 1.

 -file {string}    Name of checkpoint file (needed for restart-from-interrupt)

 -bmin {num} Log2(minimum factor to try), in floating double form.
 If > 10^9 its whole-number part is taken as the kmin value instead.

 -bmax {num} Log2(maximum factor to try), in floating double form.
 If > 10^9 its whole-number part is taken as the kmax value instead.

 -kmin {num}  Lowest factor K value to be tried in each pass ( > 0).

 -kmax {num} Highest factor K value to be tried in each pass ( < 2^64).

 -passmin {num}  Current factoring pass (0-15).

 -passmax {num}  Maximum pass for the run (0-15).
INFO: using 64-bit-significand form of floating-double rounding constant for scalar-mode DNINT emulation.

In the source code of factor.c, there's somewhat more:

Mfactor command line options:

REQUIRED:
        * One (and ONLY one) of -m|mm|f, followed by a valid numerical exponent;
        * One (and ONLY one) of -bmax|kmax, unless it's a restart, i.e. a valid checkpoint file
            for the number in question exists. Iff -bmax|kmax specified, an optional lower-bound
            argument -bmin|kmin may also be specified, which must not exceed the upper bound.
        * If neither -bmax|kmax specified, it is assumed that a valid checkpoint file
            for the number in question exists. The data in this file will indicate either
            an as-yet-uncompleted factoring run for the number in question (in which case
            the run is resumed at the point at which it left off), or a completed run. In
            the latter instance, if a -kplus argument was specified on the command line,
            the k-bounds of the previous completed run are incremented and a new run with
            k-bounds [kmax_previous, kmax_previous + kplus] is begun. If -kplus is specified
            but the restart-file data indicate an as-yet-uncompleted run, a warning is issued,
            the -kplus argument ignored, and the incomplete run is resumed.

Others are optional and in some cases mutually exclusive:

    -h          Prints this help menu and exits

    -m [int]    Trial-factor the Mersenne number M(int) = 2^int - 1, with int < 2^MAX_BITS_P.

    -mm [int]   Trial-factor the double-Mersenne number M(M(int)) = 2^(2^int) - 1, with M(int) < 2^MAX_BITS_P.

    -f [int]    Trial-factor the Fermat number F(int) = 2^(2^int) + 1, with int <= %u.\n",MAX_BITS_P.
            NOTE:
                * Fermat number Trial-factoring not currently supported (future release.)

    -bmin [float] Log2(min factor to try), in floating form (>= 0, default = 0).
    -bmax [float] Log2(max factor to try), in floating form ( < 64*NWORDS).
            NOTES:
                * If -bmin/bmax used to set lower/upper bounds for factoring, -kmin/kmax disallowed.
                * bmin/bmax form of bounds-setting only allowed for single-word-p case, since
                  multiword p may cause float approximations to p, 2*p etc to overflow.

    -kmin  [int] Lowest  factor K value to be tried in each pass ( > 0, default = 1).
    -kmax  [int] Highest factor K value to be tried in each pass ( < 2^64).
            NOTE:
                * If -kmin/kmax used to set lower/upper bounds for factoring, -bmin/bmax disallowed.

    -kplus [int] Added   factor K value to be tried in each pass ( < 2^64), for an exponent
                for which one or more previous shallower factoring runs have already been done
                (specifically, a checkpoint file for a previous run exists.)
            NOTES:
                * If -bmin/bmax or -kmin/kmax used to set bounds for factoring, -kplus disallowed (and v.v.)
                * If -kmin|kmax from a previous run of the number in question found
                 in a checkpoint file, that old kmax serves as kmin for the new run
                 and (old kmax) + (kplus) serves as kmax for the new run.

    -passmin [int]  Maximum factoring pass for the run (0-TF_PASSES-1, default =  0).
    -passmax [int]  Maximum factoring pass for the run (0-TF_PASSES-1, default = 15).
            NOTE:
                * If passmin|max from a previous run of the number in question found
                 in a checkpoint file and those pass bounds conflict with the ones
                 given via the command line, an error message is printed and the
                 run aborted. This is done as a precaution against inadvertently
                 skipping a range of trial-factoring bounds in a multipart series
                 of partial factoring runs. In this event the user shhould carefully
                 compare the checkpoint file(s) for the number in question they have
                 saved from previous runs with their current command line and modify
                 one or the other so as to remove any pass-range conflicts.

    -q [int]    A known factor for the number (only used if FAC_DEBUG def'd).

[ewmayer]

Thanks, Ken - I can't vouch for all the help menu content being 100% current, so lmk of any issues you find based on your own tests.

Also, the code emits some stuff about writing savefiles at run-start, but savefile-writing is in fact disabled. Users simply need to keep track of their own subrange testing, if they break a deep TF run into multiple work chunks.

Also, please be so kind as to post a mini-tarball of the factor.h and factor.c files you end up with as result of your build and test, and note whether those differ at all from the versions of those 2 files I sent you today. (Both of which differ from those in the current official Mlucas release - which does not even have the factor.c file, to reflect that being strictly experimental code).

[kriesel]

Originally Posted by kriesel

Program output for help is

"Poor man's multithreading" is running multiple processes for the same bit level and exponent, with different passmin and passmax. For example, 4-way, to use 4 cores with an msys2 compiled image,
passmin 0 passmin 3,
passmin 4 passmax 7,
passmin 8 passmax 11,
passmin 12 passmax 15.
This works well for powers of two passes per run. 2,4,8,16.

If the build is done with -DTF_CLASSES=4620 for finer pass granularity, then passmin and passmax ranges become 0 to 959, 960 = 2⁶ * 3 * 5 in number. This larger number of passes with numerous small factors allows for much more choice of degree of parallelism.
1,2,3,4,5,6,8,10,12,15,16,20,24,30, 32,40,48,60,64,80,96,120,160,192,240,320,480,960
For brief runs there is no point to going to high degrees of parallelism, and -DTF_CLASSES seems to introduce higher overhead into a single run. For lengthy runs, the only way to get run times reasonable may be high degrees of parallelism. Using hyperthreading helps.

[ewmayer]

I revisited the currently-disabled checkpointing code yesterday - it predates my experiments with multithreaded runs and thus needs a complete overhaul, but in silver-lining news, I believe I've found a way to do it that will serve both your "poor's man's multithreading" current run mode and a future true-multithreaded implementation. Here 2 code comments describing the schema I have in mind:

/* The factoring checkpoint file is assumed to have the format:
The file is ascii format, with the following [entries] - user-added comments or annotations are allowed below,
lines 1 and 2, as long as they do not trigger hits for the find-substring-in-file triggered by the mandatory,
program-autogenerated entries:

Line 1:	[String containing the current exponent stored in pstring.]
		Exponent must be odd (but not necessarily prime), and have digit length corresponding
		to the number * of 64-bit limbs set via -DP*WORD at build time. (-DNWORD means unlimited)
Line 2: [Value of TF_PASSES in the build (16 or 960)]

Followed by anywhere from 1 to TF_PASSES lines of the following form,
which need not be in numeric order but must have no index repeats:

Pass [index < TF_PASSES]: [Max factor-k value reached for this pass number by the run(s) which updated this savefile]

Here, "factor-k value" refers to the standard form of prime-exponent Mersenne number factors: M(p) has 1 or more
factors of form q = 2.k.p+1. Mfactor does not in fact require prime exponents, but for nonprime ones will only search
for factors of that form. For example, for the composite-exponent case M(25) = 2^25-1
*/

/*
Every 1024th pass through the small-primes sieve, and also following the final pass
through the sieve, write the checkpoint file, with format as described previously.

Since we expect that multiple jobs and/or threads may be working on the same exponent,
we make such checkpoint-updates atomic as follows:

1. job/thread X acquires file lock and opens checkpoint file <filename> for reading, if it exists.
	No other job/thread may acquire file lock until X releases it;
2. X also opens a 2nd, temporary, file <filename.tmp> for writing, beginning with line 1: exponent (= pstring)
	and line 2, Value of TF_PASSES in the build (16 or 960)
3. If there was an existing savefile found in step [1], X copies its contents
	to the .tmp file in [2] line-by-line, only updating the single "Pass *: [max k reached]" entry
	corresponding to the current pass whose progress is being saved via checkpointing;
4. X closes both files, renames <filename.tmp> to <filename>, thus overwriting the now-obsolete
	version of the latter;
5. X releases the file lock and resumes processing factor candidates.
*/

[kriesel]

Originally Posted by ewmayer

I revisited the currently-disabled checkpointing code yesterday ...
4. X closes both files, renames <filename.tmp> to <filename>, thus overwriting the now-obsolete
version of the latter;
5. X releases the file lock and resumes processing factor candidates.
*/[/code]

index and pass seem to be synonymous.
In #4, "renames <filename.tmp> to <filename>, thus overwriting the now-obsolete
version of the latter" may cause some trouble on Windows. IIRC Preda did something similar in gpuowl at times, and the rename failed on Windows but worked in linux. Windows refused to do what amounts to an implied delete.
A quick demo at the command line:

C:\Users\kkrie\documents\starfish>copy con: test.txt
asdf this is the file I want to delete by renaming something else onto it.
^Z
        1 file(s) copied.

C:\Users\kkrie\documents\starfish>copy con: testnew.txt
asdf this is the file I want to replace test.txt via the rename.
^Z
        1 file(s) copied.

C:\Users\kkrie\documents\starfish>rename testnew.txt test.txt
A duplicate file name exists, or the file
cannot be found.

C:\Users\kkrie\documents\starfish>type test.txt
asdf this is the file I want to delete by renaming something else onto  it.

Create new, save new, check save succeeded, delete old, rename new to old.

[kriesel]

Searching in the interval k=[0, 16336320]
Each of  16 (p mod 60) passes will consist of 1 intervals of length 272272

    Factor with k = 68745. This factor is a probable prime.
M(31) has 1 factors in range k = [0, 16336320], passes 0-15

That is the result of a test run with -mm 31, not -m 31 (-bmax 48 for a quick single threaded run).

Seems like the output ought to follow the same notation as the input.
I've checked the k value and it is valid for https://www.mersenne.ca/exponent/2147483647

[kriesel]

Preceding post's output error occurs in results.txt but not console output. Don't know if that's due to Ernst's source or some wayward edit at my location.


Due to typos or batch script editing oversights, it's possible to enter bmax such that the computed kmax < 1. Mfactor identifies these as possibly kmax > 2⁶⁴.

mfactor-base-nw.exe -mm 2203 -bmax 1295  1>>mm.txtINFO: using 64-bit-significand form of floating-double rounding constant for scalar-mode DNINT emulation.
Apr2015 mi64_div quicktest passes.
mi64_div quicktest passes.
INFO: No factoring savefile t2203 found ... starting from scratch.
ERROR: at line 1698 of file ../factor.c
Assertion failed: Something went wrong with the computation of kmax ... possibly your bmax implies kmax > 64-bit?

[kriesel]

Originally Posted by kriesel

Thread re Ernst's Mfactor program, primarily if not entirely cpu oriented, begins late 2005:
https://www.mersenneforum.org/showthread.php?t=4939

Another thread, re getting set up for CUDA gpu MFactor compiles on linux, begins late 2014, terminating in a batch of questions Ernst had about efficient gpu implementation:
https://www.mersenneforum.org/showthread.php?t=19457
Since that's from very early 2015, nearly 5 years ago, some of them may no longer be relevant. It's probably best to leave it alone for now, until Ernst has a chance to review/revise the list. https://www.mersenneforum.org/showpo...0&postcount=67

Are there more?

Yes. The thread about the shared KNL machine GIMPS bought contains a fair amount relating to TF, in 2016, including comparisons between mfaktc, prime95, and Mfactor factoring performance, build of Mfactor on KNL, timings versus number of parallel execution threads, discussion of op counts, etc.

[kriesel]

As part of the large reference info blog, there is an Mfactor reference thread.

[James Heinrich]

Someone submitted some results to me that show a potential bug in Mfactor.

Mfactor-base-1w.exe -bmin 57 -bmax 64 -m 7962742673

Searching in the interval k=[0, 1159878720], i.e. q=[1.000000e+000, 1.847163e+019]
Each of  16 (p mod 60) passes will consist of 71 intervals of length 272272
2949120 ones bits of 16336320 in master sieve template.
TRYQ = 4, max sieving prime = 1299721
Time to set up sieve = 00:00:00.026
pass = 0
pass = 1
pass = 2
pass = 3
pass = 4
pass = 5
pass = 6
pass = 7
pass = 8
pass = 9
pass = 10
pass = 11
        Factor with k = 26939568. This factor is a probable prime.

pass = 12
pass = 13
pass = 14Factor with k = 16336375. Program: E3.0x

        Factor with k = 16336135. This factor is a probable prime.

pass = 15
M(7962742673) has 3 factors in range k = [0, 1159878720], passes 0-15
Performed 46389508 trial divides
Clocks = 00:00:07.711

Not only is the output (both screen and log) different from the other 2 factors, but:
* 260164700669260751 (k=16336375) is not a factor of M7962742673
* 260164700669260751 = 7 × 13^2 × 41 × 5363888845417