mersenneforum.org  

Go Back   mersenneforum.org > Great Internet Mersenne Prime Search > Hardware > GPU Computing

Reply
 
Thread Tools
Old 2020-05-09, 14:08   #3257
James Heinrich
 
James Heinrich's Avatar
 
"James Heinrich"
May 2004
ex-Northern Ontario

B7616 Posts
Default

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?
James Heinrich is online now   Reply With Quote
Old 2020-05-09, 18:14   #3258
kriesel
 
kriesel's Avatar
 
"TF79LL86GIMPS96gpu17"
Mar 2017
US midwest

23·32·59 Posts
Default

Quote:
Originally Posted by James Heinrich View Post
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
8+ not found yet

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
kriesel is offline   Reply With Quote
Old 2020-05-09, 18:19   #3259
kriesel
 
kriesel's Avatar
 
"TF79LL86GIMPS96gpu17"
Mar 2017
US midwest

23×32×59 Posts
Default

Quote:
Originally Posted by TheJudger View Post
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
kriesel is offline   Reply With Quote
Old 2020-05-09, 19:25   #3260
James Heinrich
 
James Heinrich's Avatar
 
"James Heinrich"
May 2004
ex-Northern Ontario

2·32·163 Posts
Default

Quote:
Originally Posted by kriesel View Post
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 View Post
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 View Post
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.
James Heinrich is online now   Reply With Quote
Old 2020-05-09, 20:40   #3261
kriesel
 
kriesel's Avatar
 
"TF79LL86GIMPS96gpu17"
Mar 2017
US midwest

23×32×59 Posts
Default

Quote:
Originally Posted by James Heinrich View Post
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
kriesel is offline   Reply With Quote
Old 2020-05-09, 21:17   #3262
James Heinrich
 
James Heinrich's Avatar
 
"James Heinrich"
May 2004
ex-Northern Ontario

2·32·163 Posts
Default

Quote:
Originally Posted by kriesel View Post
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
James Heinrich is online now   Reply With Quote
Old 2020-05-09, 22:14   #3263
kriesel
 
kriesel's Avatar
 
"TF79LL86GIMPS96gpu17"
Mar 2017
US midwest

23·32·59 Posts
Default

Quote:
Originally Posted by James Heinrich View Post
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
kriesel is offline   Reply With Quote
Old 2020-05-09, 22:17   #3264
SethTro
 
SethTro's Avatar
 
"Seth"
Apr 2019

100110112 Posts
Default

Quote:
Originally Posted by James Heinrich View Post
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.

I think this was asked about in https://www.mersenneforum.org/showpo...postcount=1148

Last fiddled with by SethTro on 2020-05-09 at 22:18
SethTro is offline   Reply With Quote
Old 2020-05-15, 20:14   #3265
ixfd64
Bemusing Prompter
 
ixfd64's Avatar
 
"Danny"
Dec 2002
California

2,293 Posts
Default

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.
ixfd64 is offline   Reply With Quote
Old 2020-05-18, 19:17   #3266
TheJudger
 
TheJudger's Avatar
 
"Oliver"
Mar 2005
Germany

33·41 Posts
Default

Quote:
Originally Posted by kriesel View Post
(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
TheJudger is offline   Reply With Quote
Old 2020-05-18, 19:34   #3267
kriesel
 
kriesel's Avatar
 
"TF79LL86GIMPS96gpu17"
Mar 2017
US midwest

23·32·59 Posts
Default

Quote:
Originally Posted by TheJudger View Post
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
kriesel is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
mfakto: an OpenCL program for Mersenne prefactoring Bdot GPU Computing 1631 2020-08-15 10:29
The P-1 factoring CUDA program firejuggler GPU Computing 748 2019-11-23 16:36
"CUDA runtime version 0.0" when running mfaktc.exe froderik GPU Computing 4 2016-10-30 15:29
World's second-dumbest CUDA program fivemack Programming 112 2015-02-12 22:51
World's dumbest CUDA program? xilman Programming 1 2009-11-16 10:26

All times are UTC. The time now is 11:24.

Sat Aug 15 11:24:01 UTC 2020 up 2 days, 7:59, 2 users, load averages: 1.73, 1.94, 1.78

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, 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.