mersenneforum.org mfaktc: a CUDA program for Mersenne prefactoring
 Register FAQ Search Today's Posts Mark Forums Read

 2020-05-09, 14:08 #3257 James Heinrich     "James Heinrich" May 2004 ex-Northern Ontario 22×5×151 Posts I believe I know the answer, can somebody with knowledge of the source please confirm for me: How does mfaktc handle discovering composite factors? (I've been using M110393069 for testing which has a thousand composite factors) I believe mfaktc simply returns the composite factor as-discovered with no attempt to determine if said factor is composite or prime, correct? Assuming thus, a two-part question: a) how practical would it be for mfaktc to detect that a discovered factor is composite? b) if factor is composite, how practical would it be for mfaktc to split the factor into primes?
2020-05-09, 18:14   #3258
kriesel

"TF79LL86GIMPS96gpu17"
Mar 2017
US midwest

10001001110002 Posts

Quote:
 Originally Posted by James Heinrich I believe I know the answer, can somebody with knowledge of the source please confirm for me: How does mfaktc handle discovering composite factors? (I've been using M110393069 for testing which has a thousand composite factors) I believe mfaktc simply returns the composite factor as-discovered with no attempt to determine if said factor is composite or prime, correct? Assuming thus, a two-part question: a) how practical would it be for mfaktc to detect that a discovered factor is composite? b) if factor is composite, how practical would it be for mfaktc to split the factor into primes?
Wow, literally, 1013 distinct composite factors known, and 10 distinct prime factors. I thought at first the "thousand composite factors" was hyperbole.
With this in mfaktc.ini,
Code:
# possible values for StopAfterFactor:
# 0: Do not stop the current assignment after a factor was found.
# 1: When a factor was found for the current assignment stop after the
#    current bitlevel. This makes only sense when Stages is enabled.
# 2: When a factor was found for the current assignment stop after the
#    current class.
#
# Default: StopAfterFactor=1

StopAfterFactor=1
Factor=110393069,63,64 quickly returned the following:
Code:
[Sat May 09 10:09:03 2020]
UID: Kriesel/dodo-rtx2080super, M110393069 has a factor: 17743732831822018159 [TF:63:64:mfaktc 0.21 75bit_mul32_gs]
[Sat May 09 10:09:03 2020]
UID: Kriesel/dodo-rtx2080super, M110393069 has a factor: 13307799624252889361 [TF:63:64:mfaktc 0.21 75bit_mul32_gs]
[Sat May 09 10:09:03 2020]
UID: Kriesel/dodo-rtx2080super, found 2 factors for M110393069 from 2^63 to 2^64 [mfaktc 0.21 75bit_mul32_gs]
So yes, it returns composite factors, and the server breaks them down into prime factors along with or as part of its factor verification.
There's some question how many factors in one bit level increment mfaktx will find and report.
For this remarkable test exponent, more than two factors in a bit level is not an issue until 3 factors at 121-122 bits which would take quite a while to run as a test;
4 124-125
5 154-155
6,7 183-184

Such high bit levels are not supported in mfaktx, although they could be attempted with Factor5 or Ernst's Mfactor and lots of cores and patience. (Mfaktc max 95 bit factors, mfakto max 92 bits)

More than one factor per class may be an issue. If so, its overall impact on the GIMPS project is small. See https://www.mersenneforum.org/showpo...82&postcount=5
Although, up to 10 factors / class may be provided for. https://www.mersenneforum.org/showpo...4&postcount=35

Last fiddled with by kriesel on 2020-05-09 at 18:16

2020-05-09, 18:19   #3259
kriesel

"TF79LL86GIMPS96gpu17"
Mar 2017
US midwest

113816 Posts

Quote:
 Originally Posted by TheJudger Hi, good news: Yesterday I've added more than 200 known factors to the selftest. Every single factor was verified using my code. :) In some cases it misses factors when there are mutliple factors in one class close together but this is not critical. The is a known problem since the first version... This has nothing to do with the calculations itself, it is just how the results are returned from the GPU to the CPU. ----- Raw speed on my GTX 275 for M66362159 above 64 bits: ~74M candidates per second. Siever received a nice performace improvement for free by adding "-funroll-all-loops" to the gcc options. :) (only useful for CPU-limited scenarios) Oliver
(bold emphasis above is mine)
Is the issue of multiple factors in one class closely spaced causing some to be missed still present in mfaktc v0.21?
Please suggest some exponent/bitlevel combinations for test of the multiple-factors-per-class case.

Last fiddled with by kriesel on 2020-05-09 at 18:23

2020-05-09, 19:25   #3260
James Heinrich

"James Heinrich"
May 2004
ex-Northern Ontario

22×5×151 Posts

Quote:
 Originally Posted by kriesel Wow, literally, 1013 distinct composite factors known, and 10 distinct prime factors. I thought at first the "thousand composite factors" was hyperbole.
No exaggeration.
There are three exponents with 11 known factors (thereby 2036 composite factors), and nine exponents with 10 known factors, but of those really only M110393069 is in the "normal" exponent range.
https://www.mersenne.ca/manyfactors.php

Quote:
 Originally Posted by kriesel So yes, it returns composite factors, and the server breaks them down into prime factors along with or as part of its factor verification.
Yes, that is what currently happens, but I'm exploring the possibility of getting all the factoring software (Prime95, mfaktx, gpuowl, etc) modified to (ideally) return only prime factors, even when discovered as a composite.
Per your example, Factor=110393069,63,64 should ideally return something like:
Code:
M110393069 has a composite factor: 13307799624252889361 [TF:63:64:mfaktc 0.21 75bit_mul32_gs]
M110393069 has a factor: 1545502967 [TF:63:64:mfaktc 0.21 75bit_mul32_gs]
M110393069 has a factor: 8610659383 [TF:63:64:mfaktc 0.21 75bit_mul32_gs]
M110393069 has a composite factor: 17743732831822018159 [TF:63:64:mfaktc 0.21 75bit_mul32_gs]
M110393069 has a factor: 1545502967 [TF:63:64:mfaktc 0.21 75bit_mul32_gs]
M110393069 has a factor: 11480879177 [TF:63:64:mfaktc 0.21 75bit_mul32_gs]
found 3 prime factors for M110393069 from 2^63 to 2^64 [mfaktc 0.21 75bit_mul32_gs]
Out of necessity, the server does break down any composite factors submitted, but it would be better if this could be done at the client level (without removing the server-level checks of course).

Quote:
 Originally Posted by kriesel Is the issue of multiple factors in one class closely spaced causing some to be missed still present in mfaktc v0.21? Please suggest some exponent/bitlevel combinations for test of the multiple-factors-per-class case.
There is no shortage of examples of exponents with multiple known factors that share a 4620-class, to quote just the ones from 100M:
Code:
100028477
100062071
100071661
100104131
100118399
100250341
100269131
100296149
100297643
100331219
100444901
100475647
100499617
100621361
100683689
100709621
If you need a more extensive test-case list email me and I can give you a large list.
Exponents with three factors sharing a class are rare, these are the only four I found and they're all quite small:
Code:
150551
329009
4965187
12671587
Of course, if this bug causes factors to be missed, then they wouldn't be in my list.

2020-05-09, 20:40   #3261
kriesel

"TF79LL86GIMPS96gpu17"
Mar 2017
US midwest

23·19·29 Posts

Quote:
 Originally Posted by James Heinrich There is no shortage of examples of exponents with multiple known factors that share a 4620-class, to quote just the ones from 100M: Code: 100028477 ... 100709621 If you need a more extensive test-case list email me and I can give you a large list. Exponents with three factors sharing a class are rare, these are the only four I found and they're all quite small: Code: 150551 329009 4965187 12671587 Of course, if this bug causes factors to be missed, then they wouldn't be in my list.
Thanks for the lists, however, what I was trying to express was an interest in any known cases of mersenne numbers with prime exponents within mersenne.ca exponent range, preferably within mersenne.org range (p<109) with multiple factors known for {same-exponent & same-bit-level & same-class-number} trifecta / slot-machine-jackpot, of bit size no larger than GIMPS would TF to normally on a gpu, which would be 76 to 92 bits or so depending on exponent. (Think intersection of 5 or 6 sets.)
That's what it would take for mfaktc or mfakto to encounter the case where normal use leads to two factors in the same class of the same bit level of the same exponent in the same run, and theoretically finding and reporting two or more factors from that single exponent, bit level, class pass.

For an exponent p, p prime, a bit level x-1 to x, x <= normal GIMPS factoring depth for p, a class any ONE of 420 or 4620, multiple factors found. Possibly even multiple factors within one block given to one of the many gpu multiprocessors.

Instead of at the mfaktc console output,
Code:
May 09 10:09 | 2271  49.5% |  0.001    n.a. |   1600.63    82485    n.a.%
M110393069 has a factor: 17743732831822018159
May 09 10:09 | 2272  49.6% |  0.001    n.a. |   1600.63    82485    n.a.%
...
May 09 10:09 | 2860  62.4% |  0.001    n.a. |   1600.63    82485    n.a.%
M110393069 has a factor: 13307799624252889361
May 09 10:09 | 2872  62.5% |  0.001    n.a. |   1600.63    82485    n.a.%
it might look something like
Code:
May 09 10:09 | 2271  49.5% |  0.001    n.a. |   1600.63    82485    n.a.%
M110393069 has a factor: 17743732831822018159
M110393069 has a factor: ‭17743733851853975719‬
May 09 10:09 | 2272  49.6% |  0.001    n.a. |   1600.63    82485    n.a.%
(That second, underlined one is completely fictitious)
I roughly estimated (in the attachment at https://www.mersenneforum.org/showpo...82&postcount=5) that we should find hundreds or thousands of such over the full scope of mersenne.org TF. If we can't identify any coincident class, bit level, exponent multiple factor finds, given how much TF has already been done, we're probably missing some (relatively few) factors this way.

Last fiddled with by kriesel on 2020-05-09 at 20:47

2020-05-09, 21:17   #3262
James Heinrich

"James Heinrich"
May 2004
ex-Northern Ontario

22·5·151 Posts

Quote:
 Originally Posted by kriesel Thanks for the lists, however, what I was trying to express was an interest in any known cases of mersenne numbers with prime exponents within mersenne.ca exponent range, preferably within mersenne.org range (p<109) with multiple factors known for {same-exponent & same-bit-level & same-class-number} trifecta
Sorry, I forgot to filter it to same-bitlevel. That makes the list much shorter (and longer to search) but I still found 4 examples in the ~100M range:
Code:
106266857
109013999
109088341
109405193
I only searched in 100M<110M, if you want I can expand the search to find all the examples in GIMPS range, but that'll about an hour of hammering the database.

edit: it actually didn't take as long as I feared, here's the complete list of 215 GIMPS-range exponents with same-bits-and-class factors:
Code:
Factor=630907,49,50
Factor=666493,58,59
Factor=754463,49,50
Factor=976301,49,50
Factor=3902347,37,38
Factor=5279899,42,43
Factor=12953419,49,50
Factor=13904749,45,46
Factor=14298527,54,55
Factor=14749391,68,69
Factor=15162197,41,42
Factor=16892969,62,63
Factor=21474083,40,41
Factor=21633289,51,52
Factor=23740537,55,56
Factor=26936579,39,40
Factor=28247707,56,57
Factor=29235029,60,61
Factor=33838793,61,62
Factor=40917917,47,48
Factor=42416729,59,60
Factor=45632189,45,46
Factor=47916989,60,61
Factor=49678099,65,66
Factor=55346957,62,63
Factor=68168081,62,63
Factor=68989909,52,53
Factor=74542373,65,66
Factor=80374999,54,55
Factor=88079011,45,46
Factor=95469713,66,67
Factor=95669209,63,64
Factor=97267133,46,47
Factor=106266857,63,64
Factor=109013999,53,54
Factor=109088341,53,54
Factor=109405193,54,55
Factor=119525743,49,50
Factor=121156699,51,52
Factor=122522789,57,58
Factor=122617237,53,54
Factor=148380737,50,51
Factor=153225187,64,65
Factor=155676707,54,55
Factor=157910509,60,61
Factor=158599201,57,58
Factor=160739149,64,65
Factor=168830449,50,51
Factor=169014941,59,60
Factor=170473691,59,60
Factor=171953321,64,65
Factor=186375971,45,46
Factor=188904787,54,55
Factor=191462893,61,62
Factor=194559377,59,60
Factor=200995609,48,49
Factor=208394701,58,59
Factor=211943939,65,66
Factor=214423889,62,63
Factor=229769411,48,49
Factor=230055593,63,64
Factor=232507777,62,63
Factor=234028031,43,44
Factor=238430009,65,66
Factor=247462603,50,51
Factor=247575857,61,62
Factor=248693219,61,62
Factor=249720929,58,59
Factor=257601991,53,54
Factor=269222717,59,60
Factor=291566903,51,52
Factor=296611769,63,64
Factor=304843843,50,51
Factor=307436693,63,64
Factor=311095511,64,65
Factor=329514313,51,52
Factor=333341903,57,58
Factor=339049663,45,46
Factor=344226053,50,51
Factor=349871771,44,45
Factor=350800537,49,50
Factor=351511079,59,60
Factor=359812081,48,49
Factor=363424847,47,48
Factor=371542393,49,50
Factor=376397243,45,46
Factor=384190957,46,47
Factor=384327743,56,57
Factor=384394709,55,56
Factor=385356109,53,54
Factor=387013937,60,61
Factor=400835159,51,52
Factor=401102021,52,53
Factor=403918327,54,55
Factor=404784839,61,62
Factor=406884479,53,54
Factor=408071501,44,45
Factor=408188827,69,70
Factor=412778909,60,61
Factor=413747153,54,55
Factor=414824231,60,61
Factor=419128607,57,58
Factor=448196831,55,56
Factor=452020073,43,44
Factor=454609277,63,64
Factor=457729901,62,63
Factor=459228547,54,55
Factor=460167947,47,48
Factor=466220519,57,58
Factor=482584937,63,64
Factor=483370357,59,60
Factor=492464549,64,65
Factor=496423661,55,56
Factor=506824429,48,49
Factor=506895563,62,63
Factor=512880491,57,58
Factor=521816593,53,54
Factor=524087329,46,47
Factor=526005499,49,50
Factor=526014143,58,59
Factor=530664289,46,47
Factor=555551489,67,68
Factor=556353643,48,49
Factor=562335937,54,55
Factor=563680291,55,56
Factor=573868573,47,48
Factor=575599867,46,47
Factor=576806761,57,58
Factor=589429417,55,56
Factor=589746037,46,47
Factor=600953513,59,60
Factor=603618313,60,61
Factor=609388763,48,49
Factor=610146851,63,64
Factor=611741059,63,64
Factor=617863849,48,49
Factor=625400089,54,55
Factor=625521709,61,62
Factor=636713333,56,57
Factor=638366929,60,61
Factor=640381303,50,51
Factor=648452527,62,63
Factor=650749717,53,54
Factor=650927363,54,55
Factor=658195159,50,51
Factor=660280373,60,61
Factor=663891329,53,54
Factor=664600039,61,62
Factor=669290053,57,58
Factor=670620989,49,50
Factor=673902499,53,54
Factor=676343021,64,65
Factor=676611721,43,44
Factor=677065223,54,55
Factor=682014161,64,65
Factor=684732073,59,60
Factor=686029517,63,64
Factor=689997797,44,45
Factor=694678529,45,46
Factor=699891781,54,55
Factor=705410129,61,62
Factor=712472153,47,48
Factor=716225651,48,49
Factor=718763291,43,44
Factor=722281877,48,49
Factor=722671237,63,64
Factor=729992177,57,58
Factor=734571463,52,53
Factor=736663073,57,58
Factor=740774491,47,48
Factor=744550061,60,61
Factor=763981891,64,65
Factor=769814911,49,50
Factor=772482437,52,53
Factor=773120087,48,49
Factor=773476307,46,47
Factor=775692791,44,45
Factor=786451073,61,62
Factor=793651759,54,55
Factor=799473617,45,46
Factor=821119861,52,53
Factor=822585289,48,49
Factor=824575069,46,47
Factor=827289787,49,50
Factor=827753587,69,70
Factor=829322971,53,54
Factor=829364051,62,63
Factor=838613569,48,49
Factor=843158347,48,49
Factor=845831837,57,58
Factor=853745551,47,48
Factor=854811127,58,59
Factor=865444469,50,51
Factor=871148027,53,54
Factor=873514913,58,59
Factor=888502117,56,57
Factor=891816469,51,52
Factor=897478951,45,46
Factor=900842653,63,64
Factor=915151613,65,66
Factor=918760987,57,58
Factor=920280619,49,50
Factor=922496633,58,59
Factor=927602177,54,55
Factor=940010633,50,51
Factor=941381677,52,53
Factor=947056163,54,55
Factor=948726797,63,64
Factor=956418803,47,48
Factor=965694907,62,63
Factor=968105849,44,45
Factor=981595297,50,51
Factor=985010921,51,52
Factor=986248531,45,46
Factor=996709397,46,47

Last fiddled with by James Heinrich on 2020-05-09 at 22:01

2020-05-09, 22:14   #3263
kriesel

"TF79LL86GIMPS96gpu17"
Mar 2017
US midwest

23·19·29 Posts

Quote:
 Originally Posted by James Heinrich Sorry, I forgot to filter it to same-bitlevel. That makes the list much shorter (and longer to search) but I still found 4 examples in the ~100M range: Code: 106266857 109013999 109088341 109405193 I only searched in 100M<110M, if you want I can expand the search to find all the examples in GIMPS range, but that'll about an hour of hammering the database. edit: it actually didn't take as long as I feared, here's the complete list of 215 GIMPS-range exponents with same-bits-and-class factors: Code: Factor=630907,49,50 ... Factor=996709397,46,47
About 10 of those coincident factor cases are above 65 bits, and my rough estimate was 124 such for more-classes and completed to GIMPS bit levels TF; 1243 for less-classes.

Thanks, while you were getting the big list, I ran the first test case. Console output

Code:
May 09 17:02 | 3607  78.1% |  0.216    n.a. |      7.70    82485    n.a.%
M106266857 has a factor: 15207927026741198039
M106266857 has a factor: 16752154502925095159
May 09 17:02 | 3615  78.2% |  0.217    n.a. |      7.66    82485    n.a.%
Results file
Code:
[Sat May 09 17:02:15 2020]
UID: Kriesel/dodo-rtx2080super, M106266857 has a factor: 15207927026741198039 [TF:63:64:mfaktc 0.21 75bit_mul32_gs]
UID: Kriesel/dodo-rtx2080super, M106266857 has a factor: 16752154502925095159 [TF:63:64:mfaktc 0.21 75bit_mul32_gs]
[Sat May 09 17:02:57 2020]
UID: Kriesel/dodo-rtx2080super, found 2 factors for M106266857 from 2^63 to 2^64 [mfaktc 0.21 75bit_mul32_gs]

Last fiddled with by kriesel on 2020-05-09 at 22:43

2020-05-09, 22:17   #3264
SethTro

"Seth"
Apr 2019

101000012 Posts

Quote:
 Originally Posted by James Heinrich No exaggeration. There are three exponents with 11 known factors (thereby 2036 composite factors), and nine exponents with 10 known factors, but of those really only M110393069 is in the "normal" exponent range. https://www.mersenne.ca/manyfactors.php Yes, that is what currently happens, but I'm exploring the possibility of getting all the factoring software (Prime95, mfaktx, gpuowl, etc) modified to (ideally) return only prime factors, even when discovered as a composite. Per your example, Factor=110393069,63,64 should ideally return something like: Code: M110393069 has a composite factor: 13307799624252889361 [TF:63:64:mfaktc 0.21 75bit_mul32_gs] M110393069 has a factor: 1545502967 [TF:63:64:mfaktc 0.21 75bit_mul32_gs] M110393069 has a factor: 8610659383 [TF:63:64:mfaktc 0.21 75bit_mul32_gs] M110393069 has a composite factor: 17743732831822018159 [TF:63:64:mfaktc 0.21 75bit_mul32_gs] M110393069 has a factor: 1545502967 [TF:63:64:mfaktc 0.21 75bit_mul32_gs] M110393069 has a factor: 11480879177 [TF:63:64:mfaktc 0.21 75bit_mul32_gs] found 3 prime factors for M110393069 from 2^63 to 2^64 [mfaktc 0.21 75bit_mul32_gs] Out of necessity, the server does break down any composite factors submitted, but it would be better if this could be done at the client level (without removing the server-level checks of course).
I have some knowledge here (I found one of the factors of 110393069).

It's really easy to detect if a factor is composite because all factors are of the form (2*k*p+1) so if the factor is composite it must be of the form (2*k_1*p+1)*(2*k_2*p+1) which restricts k_1 and k_2 to be very small so it's easy to just check if the returned factor is divisible by (2*i*p+1) for i <= 1000. I asked about adding this to mfaktc but mfaktc doesn't have good client side big int support so I never coded it up.

Last fiddled with by SethTro on 2020-05-09 at 22:18

 2020-05-15, 20:14 #3265 ixfd64 Bemusing Prompter     "Danny" Dec 2002 California 2×1,151 Posts Silly question: what's the difference between a block and a grid? I've seen these terms used interchangeably, but my understanding is that they are different things.
2020-05-18, 19:17   #3266
TheJudger

"Oliver"
Mar 2005
Germany

33×41 Posts

Quote:
 Originally Posted by kriesel (bold emphasis above is mine) Is the issue of multiple factors in one class closely spaced causing some to be missed still present in mfaktc v0.21?
Yes, using atomics on CC 2.0 devices or newer. Current artificial limit is 10 factors within class in a single "stage".

Oliver

2020-05-18, 19:34   #3267
kriesel

"TF79LL86GIMPS96gpu17"
Mar 2017
US midwest

23×19×29 Posts

Quote:
 Originally Posted by TheJudger Yes, using atomics on CC 2.0 devices or newer. Current artificial limit is 10 factors within class in a single "stage". Oliver
Thanks. I think the probability of more than 10 factors for a single exponent/bitlevel/class is very low. I compute the odds of 6 factors per bit level and exponent to be rather small. https://www.mersenneforum.org/showth...982#post520982

 Similar Threads Thread Thread Starter Forum Replies Last Post Bdot GPU Computing 1634 2020-09-10 21:40 firejuggler GPU Computing 752 2020-09-08 16:15 froderik GPU Computing 4 2016-10-30 15:29 fivemack Programming 112 2015-02-12 22:51 xilman Programming 1 2009-11-16 10:26

All times are UTC. The time now is 01:42.

Sun Sep 20 01:42:11 UTC 2020 up 9 days, 22:53, 0 users, load averages: 0.93, 1.10, 1.17