mfaktc: a CUDA program for Mersenne prefactoring - Page 297

James Heinrich · 2020-05-09, 14:08

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?

kriesel · 2020-05-09, 18:14

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

kriesel · 2020-05-09, 18:19

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.

James Heinrich · 2020-05-09, 19:25

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:

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:

Of course, if this bug causes factors to be missed, then they wouldn't be in my list.

kriesel · 2020-05-09, 20:40

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:

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<10⁹) 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.

James Heinrich · 2020-05-09, 21:17

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<10⁹) 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:

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

kriesel · 2020-05-09, 22:14

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:

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]

SethTro · 2020-05-09, 22:17

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.

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

ixfd64 · 2020-05-15, 20:14

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.

TheJudger · 2020-05-18, 19:17

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

kriesel · 2020-05-18, 19:34

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
mfakto: an OpenCL program for Mersenne prefactoring	Bdot	GPU Computing	1676	2021-06-30 21:23
The P-1 factoring CUDA program	firejuggler	GPU Computing	753	2020-12-12 18:07
gr-mfaktc: a CUDA program for generalized repunits prefactoring	MrRepunit	GPU Computing	32	2020-11-11 19:56
mfaktc 0.21 - CUDA runtime wrong	keisentraut	Software	2	2020-08-18 07:03
World's second-dumbest CUDA program	fivemack	Programming	112	2015-02-12 22:51

2020-05-09, 14:08	#3257
James Heinrich "James Heinrich" May 2004 ex-Northern Ontario 11·311 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-15, 20:14	#3265
ixfd64 Bemusing Prompter "Danny" Dec 2002 California 95B₁₆ 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.