mersenneforum.org gr-mfaktc: a CUDA program for generalized repunits prefactoring
 User Name Remember Me? Password
 Register FAQ Search Today's Posts Mark Forums Read

2020-04-15, 08:59   #23
kriesel

"TF79LL86GIMPS96gpu17"
Mar 2017
US midwest

19C216 Posts

Quote:
 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.

2020-04-15, 09:08   #24
kriesel

"TF79LL86GIMPS96gpu17"
Mar 2017
US midwest

659410 Posts

Quote:
 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.

Last fiddled with by kriesel on 2020-04-15 at 09:17

2020-09-20, 20:13   #25
MrRepunit

Mar 2011
Germany

97 Posts

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
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!
Running from the command line would be like
Code:
./gr-mfaktc.exe -tf -97 4956227 1 64
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
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}
Unfortunately due to the specific CUDA implementation not all relations can be used in gr-mfaktc.

Have fun. Cheers,
Danilo
Attached Files
 gr-mfaktc-2020-09-20.zip (1.90 MB, 272 views)

Last fiddled with by MrRepunit on 2020-09-20 at 20:15

 2020-11-09, 08:44 #26 9970   Nov 2020 Russia 210 Posts 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 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] mprime 30.3 Code: 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?
2020-11-10, 08:17   #27
Batalov

"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

232068 Posts

Quote:
 Originally Posted by 9970 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
There is no contradiction here.
R10211584161 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 R10211584161

 2020-11-10, 09:48 #28 9970   Nov 2020 Russia 28 Posts Thank you, it worked I changed the line with the assignment in worktodo.txt to Code: Factor=bla,base=2,211584161,71,72 Added base=2
 2020-11-10, 23:57 #29 Batalov     "Serge" Mar 2008 Phi(4,2^7658614+1)/2 232068 Posts 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).
2020-11-11, 07:33   #30
ixfd64
Bemusing Prompter

"Danny"
Dec 2002
California

2,467 Posts

Quote:
 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:

Quote:
 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...

Last fiddled with by ixfd64 on 2020-11-11 at 22:02

2020-11-11, 14:36   #31
James Heinrich

"James Heinrich"
May 2004
ex-Northern Ontario

3,733 Posts

Quote:
 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.

2020-11-11, 19:36   #32
kriesel

"TF79LL86GIMPS96gpu17"
Mar 2017
US midwest

19C216 Posts

Quote:
 Originally Posted by 9970 I changed the line with the assignment in worktodo.txt to Code: 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.

Last fiddled with by kriesel on 2020-11-11 at 19:36

2020-11-11, 19:56   #33
James Heinrich

"James Heinrich"
May 2004
ex-Northern Ontario

3,733 Posts

Quote:
 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.

 Similar Threads Thread Thread Starter Forum Replies Last Post TheJudger GPU Computing 3541 2022-04-21 22:37 Bdot GPU Computing 1684 2022-04-19 20:25 firejuggler GPU Computing 753 2020-12-12 18:07 fivemack Programming 112 2015-02-12 22:51 xilman Programming 1 2009-11-16 10:26

All times are UTC. The time now is 23:46.

Mon Jul 4 23:46:02 UTC 2022 up 81 days, 21:47, 0 users, load averages: 1.48, 1.47, 1.35

Copyright ©2000 - 2022, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.

≠ ± ∓ ÷ × · − √ ‰ ⊗ ⊕ ⊖ ⊘ ⊙ ≤ ≥ ≦ ≧ ≨ ≩ ≺ ≻ ≼ ≽ ⊏ ⊐ ⊑ ⊒ ² ³ °
∠ ∟ ° ≅ ~ ‖ ⟂ ⫛
≡ ≜ ≈ ∝ ∞ ≪ ≫ ⌊⌋ ⌈⌉ ∘ ∏ ∐ ∑ ∧ ∨ ∩ ∪ ⨀ ⊕ ⊗ 𝖕 𝖖 𝖗 ⊲ ⊳
∅ ∖ ∁ ↦ ↣ ∩ ∪ ⊆ ⊂ ⊄ ⊊ ⊇ ⊃ ⊅ ⊋ ⊖ ∈ ∉ ∋ ∌ ℕ ℤ ℚ ℝ ℂ ℵ ℶ ℷ ℸ 𝓟
¬ ∨ ∧ ⊕ → ← ⇒ ⇐ ⇔ ∀ ∃ ∄ ∴ ∵ ⊤ ⊥ ⊢ ⊨ ⫤ ⊣ … ⋯ ⋮ ⋰ ⋱
∫ ∬ ∭ ∮ ∯ ∰ ∇ ∆ δ ∂ ℱ ℒ ℓ
𝛢𝛼 𝛣𝛽 𝛤𝛾 𝛥𝛿 𝛦𝜀𝜖 𝛧𝜁 𝛨𝜂 𝛩𝜃𝜗 𝛪𝜄 𝛫𝜅 𝛬𝜆 𝛭𝜇 𝛮𝜈 𝛯𝜉 𝛰𝜊 𝛱𝜋 𝛲𝜌 𝛴𝜎𝜍 𝛵𝜏 𝛶𝜐 𝛷𝜙𝜑 𝛸𝜒 𝛹𝜓 𝛺𝜔