mersenneforum.org

mersenneforum.org (https://www.mersenneforum.org/index.php)
-   GPU Computing (https://www.mersenneforum.org/forumdisplay.php?f=92)
-   -   gr-mfaktc: a CUDA program for generalized repunits prefactoring (https://www.mersenneforum.org/showthread.php?t=24901)

kriesel 2020-04-15 08:59

[QUOTE=storm5510;532948]An example: I have a very old factoring program called Factor5. It uses the CPU only.[/QUOTE]Mfactor is faster, another cpu-based program.

kriesel 2020-04-15 09:08

[QUOTE=MrRepunit;529384]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
[/QUOTE]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 2020-09-20 20:13

1 Attachment(s)
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
[CODE]./gr-mfaktc.exe -st[/CODE]It should give after some minutes and many lines of output
[CODE]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!
[/CODE]Running from the command line would be like
[CODE]./gr-mfaktc.exe -tf -97 4956227 1 64[/CODE]If you want to use the worktodo.txt file it should be filled with lines like
[CODE]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[/CODE]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:
[CODE]
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}
[/CODE]Unfortunately due to the specific CUDA implementation not all relations can be used in gr-mfaktc.


Have fun. Cheers,
Danilo

9970 2020-11-09 08:44

I found some problem.
In the result [I]gr-mfaktc 0.21[/I] I get factor. When I run [I]mprime 30.3[/I] I don't get factor.
Sample:
gr-mfacktc 0.21
[CODE]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][/CODE]mprime 30.3
[CODE]M211584161 no factor from 2^73 to 2^74, Wh8: bla, AID: bla[/CODE]When I run [I]./gr-mfaktc.exe -st[/I] all tests are running successfully. I have Ubuntu 20.04


Error in the [I]gr-mfaktc[/I] or maybe the settings need to be changed?

Batalov 2020-11-10 08:17

[QUOTE=9970;562695]
[CODE]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[/CODE][/QUOTE]
There is no contradiction here.
R[SUB]10[/SUB]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.
[C]F=11109304798164647139787;
print(Mod(10,F)^211584161-1)[/C]
Download gp, start gp, run these two lines.
The result indeed confirms that it = 0, ergo F does divide R[SUB]10[/SUB]211584161

9970 2020-11-10 09:48

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

[CODE]Factor=bla,[B]base=2[/B],211584161,71,72[/CODE]
Added [B]base=2[/B]

Batalov 2020-11-10 23:57

Then you turned it into [C]mfaktc[/C] (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 [C]mfaktc[/C]. 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 [C]mfaktc[/C] (where base=2 as a constant throughout the code, by definition).

ixfd64 2020-11-11 07:33

[QUOTE=Batalov;562866]Then you turned it into [C]mfaktc[/C] (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 [C]mfaktc[/C]. 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 [C]mfaktc[/C] (where base=2 as a constant throughout the code, by definition).[/QUOTE]

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

[QUOTE=MrRepunit;529554]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...[/QUOTE]

James Heinrich 2020-11-11 14:36

[QUOTE=9970;562796]Thank you, it worked. I changed the line with the assignment in [I]worktodo.txt to[/I] Added [B]base=2[/B][/QUOTE]This is not the program you want for Mersenne factoring. Please use the normal [url=https://download.mersenne.ca/mfaktc/mfaktc-0.21]mfaktc v0.21[/url].

kriesel 2020-11-11 19:36

[QUOTE=9970;562796]
I changed the line with the assignment in [I]worktodo.txt to[/I]

[CODE]Factor=bla,[B]base=2[/B],211584161,71,72[/CODE]Added [B]base=2[/B][/QUOTE][URL]https://www.mersenne.org/report_exponent/?exp_lo=211584161&exp_hi=&full=1[/URL] shows it was already factored to 74 bits, days before the quoted post.

James Heinrich 2020-11-11 19:56

[QUOTE=kriesel;562927][M]M211584161[/M] shows it was already factored to 74 bits, days before the quoted post.[/QUOTE]Actually the record of factoring 73-74 is the same user ([url=https://www.mersenneforum.org/member.php?u=16557]b9970[/url]). I have had some discussions with him, and he promises to use the normal mfaktc now for his Mersenne TF work.


All times are UTC. The time now is 07:16.

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2022, Jelsoft Enterprises Ltd.