gr-mfaktc: a CUDA program for generalized repunits prefactoring

[kriesel]

Originally Posted by storm5510

An example: I have a very old factoring program called Factor5. It uses the CPU only.

Mfactor is faster, another cpu-based program.

[kriesel]

Originally Posted by MrRepunit

Hi,
finally I completed the generalized repunit version of mfaktc.

Changes compared to mfaktc-0.21:
- implemented factoring of generalized repunits
- Removed Barrett and 72 bit kernels
- Removed Wagstaff related stuff
- Added 64 bit kernels
- Compiling with more-classes flag seem to be slightly faster, thus it is switched on
- allowed are all bases >= 2, program might crash if base is larger than roughly 100,000
- implemented special cases for bases 2, 3, 5, 6, 7, 8, 10, 11, 12
- dropped lower limit for exponents from 100,000 to 50,000

Nice work.
Presumably this has the same 32-bit exponent limit as mfaktc.
If you have any plans to take that higher, a 67-bit limit would be useful for a couple of exponents I've been trying to factor lately. (I'm currently using Mfactor for those. Mmff is not suitable for them since they are not double-mersennes.) Since there would be a performance hit, it's probably best to keep the 32-bit-exponent version available.

[MrRepunit]

Good news, finally I was able to implement negative bases.
Also the problem with the 1660 card should be fixed now.
I attached the source code and 64 bit binaries for Linux and Windows.


As usual test first if all tests are running successfully with

./gr-mfaktc.exe -st

It should give after some minutes and many lines of output

Selftest statistics
  number of tests           49113
  successfull tests         49113

  kernel             | success |   fail
  -------------------+---------+-------
  UNKNOWN kernel     |      0  |      0
  64bit_mul32        |   8631  |      0
  75bit_mul32        |   9710  |      0
  95bit_mul32        |   9915  |      0
  64bit_mul32_gs     |   6188  |      0
  75bit_mul32_gs     |   7246  |      0
  95bit_mul32_gs     |   7423  |      0

selftest PASSED!

Running from the command line would be like

./gr-mfaktc.exe -tf -97 4956227 1 64

If you want to use the worktodo.txt file it should be filled with lines like

Factor=4763923,60,61
Factor=base=-127,1055167,1,64
Factor=base=-97,1055167,1,64
Factor=base=17,1055167,1,64
Factor=base=10,1055167,1,64
Factor=4763923,60,61

If no base is given the default is base 10.

Some additional notes: I wrote a Mathematica notebook that allows to calculate the allowed remainders for any base. The script's source code can be extracted from the file allowed-remainders-data.c I give some results here:

base -> {{<remainder list>}, <modulo value>}
-----------------------------------------------------------------
-13 -> {{1, 7, 9, 11, 15, 17, 19, 25, 29, 31, 47, 49}, 52}
-12 -> {{1, 7, 13, 19}, 24}}
-11 -> {{1, 3, 5, 9, 15, 23, 25, 27, 31, 37}, 44}
-10 -> {{1, 7, 9, 11, 13, 19, 23, 37}, 40}
-2 -> {{1, 3}, 8}
2 -> {{1, 7}, 8}
10 -> {{1, 3, 9, 13, 27, 31, 37, 39}, 40}
11 -> {{1, 5, 7, 9, 19, 25, 35, 37, 39, 43}, 44}
12 -> {{1, 11, 13, 23}, 24}
13 -> {{1, 3, 4, 9, 10, 12}, 13}

Unfortunately due to the specific CUDA implementation not all relations can be used in gr-mfaktc.


Have fun. Cheers,
Danilo

[9970]

I found some problem.
In the result gr-mfaktc 0.21 I get factor. When I run mprime 30.3 I don't get factor.
Sample:
gr-mfacktc 0.21

R[10]211584161 has a factor: 11109304798164647139787 [TF:73:74:mfaktc 0.21 75bit_mul32_gs]
 found 1 factor for R[10]211584161 from 2^73 to 2^74 [mfaktc 0.21 75bit_mul32_gs]

mprime 30.3

M211584161 no factor from 2^73 to 2^74, Wh8: bla, AID: bla

When I run ./gr-mfaktc.exe -st all tests are running successfully. I have Ubuntu 20.04


Error in the gr-mfaktc or maybe the settings need to be changed?

[Batalov]

Originally Posted by 9970

R[10]211584161 has a factor: 11109304798164647139787 [TF:73:74:mfaktc 0.21 75bit_mul32_gs]
M211584161 no factor from 2^73 to 2^74, Wh8: bla, AID: bla

There is no contradiction here.
R₁₀211584161 is a shorthand for (10^211584161-1)/9. That's 211584161 "ones" in decimal notation.
M211584161 is a shorthand for 2^211584161-1. That's 211584161 "ones" in binary notation (and a much smaller number).
Two different numbers. One has a factor and the other does not.

You can test, using Pari/GP.
F=11109304798164647139787;
print(Mod(10,F)^211584161-1)
Download gp, start gp, run these two lines.
The result indeed confirms that it = 0, ergo F does divide R₁₀211584161

[9970]

Thank you, it worked
I changed the line with the assignment in worktodo.txt to

Factor=bla,base=2,211584161,71,72

Added base=2

[Batalov]

Then you turned it into mfaktc (which is its parent program).
Trouble is that more universal programs need extra registers to hold variables (that are in the stricter program a constant), and the class selection/enumeration code is probably more involved than in its parent mfaktc. Are the registers going to be used better or worse when you are compiling a program that does more? Have you run timing tests?

So it is unclear if this is simply slower than to run strict mfaktc (where base=2 as a constant throughout the code, by definition).

[ixfd64]

Originally Posted by Batalov

Then you turned it into mfaktc (which is its parent program).
Trouble is that more universal programs need extra registers to hold variables (that are in the stricter program a constant), and the class selection/enumeration code is probably more involved than in its parent mfaktc. Are the registers going to be used better or worse when you are compiling a program that does more? Have you run timing tests?

So it is unclear if this is simply slower than to run strict mfaktc (where base=2 as a constant throughout the code, by definition).

gr-mfaktc with base=2 is slower than vanilla mfaktc because the former currently uses a different code path for Mersenne numbers:

Originally Posted by MrRepunit

For now yes. At a later point I might create a version that uses the original code path for Mersenne primes, probably once I have included negative bases...

[James Heinrich]

Originally Posted by 9970

Thank you, it worked. I changed the line with the assignment in worktodo.txt to Added base=2

This is not the program you want for Mersenne factoring. Please use the normal mfaktc v0.21.

[kriesel]

Originally Posted by 9970

I changed the line with the assignment in worktodo.txt to

Factor=bla,base=2,211584161,71,72

Added base=2

https://www.mersenne.org/report_expo...exp_hi=&full=1 shows it was already factored to 74 bits, days before the quoted post.

[James Heinrich]

Originally Posted by kriesel

M211584161 shows it was already factored to 74 bits, days before the quoted post.

Actually the record of factoring 73-74 is the same user (b9970). I have had some discussions with him, and he promises to use the normal mfaktc now for his Mersenne TF work.