Trial division with CUDA (mmff) -- used, but runs like new!

[Dubslow]

Originally Posted by ATH

My "raw rate" was around 368 M/s (and later dropped to 347 M/s), so I figured this range would take: (1200e12-2^50)/368e6 = 201e3 sec = 56h. But it finished after 12h4min! So my k-rate was (1200e12-2^50)/43440sec = 1706 M/s ?

So I noticed each output line says "candidates 16.04G" and took rougly 43-46s so thats where the "raw rate" of 347M/s - 368M/s comes from, but what is that measuring exactly? Candidates is number of probable primes to test divisibility with?

Starting trial factoring of k*2^46+1 in k range: 1125899906842624 to 12000000000
00000 (97-bit factors)
 k_min = 1125899906842624
 k_max = 1200000000000000
Using GPU kernel "mfaktc_barrett108_F32_63gs"
    class | candidates |    time |    ETA | raw  rate | SievePrimes | CPU wait
   3/4620 |     16.04G | 43.589s | 11h36m | 367.96M/s |      210485
.
.
4613/4620 |     16.04G | 46.216s |  0m00s | 347.04M/s |      210485
no factor for k*2^46+1 in k range: 1125899906842624 to 1200000000000000 (97-bit
factors) [mmff 0.26 mfaktc_barrett108_F32_63gs]
tf(): total time spent: 12h  4m  0.423s

The sieving eliminates k-candidates whose factor q is divisible by small primes. The rest are then trial-divided into the various Fermat numbers; judging by your k-count ETA, it seems that only a 5th of the potential q's escaped the small-prime-sieve whole. The raw rate, then, is how fast the card is trial dividing the remaining q. (If you used the compile time option to disable the sieve, then the card would trial-divide every candidate, and the run would probably be about as long as you originally estimated.)

[Prime95]

Originally Posted by ATH

I tested with ranges of 1e10 and it seems the higher the k the higher risk of the error happening but sometimes you don't get the error. The lowest I have got it at was k=280,000e12.

Here is 3 instances of the error with the -v 3 option:
MM127error.txt

That was an easy fix. Note that in your output mmff is testing 187-bit factors with the barrett185 kernel. I fixed the typo so that mmff uses the 188-bit kernel, fixed a typo in the never-before-tested barrett188 kernel, and it's good to go. I'll release v. 0.27 after looking at Batalov's work. In the meantime, do not look for factors of MM127 that are more than 185 bits.

[Prime95]

Originally Posted by ATH

My "raw rate" was around 368 M/s (and later dropped to 347 M/s), so I figured this range would take: (1200e12-2^50)/368e6 = 201e3 sec = 56h. But it finished after 12h4min! So my k-rate was (1200e12-2^50)/43440sec = 1706 M/s ?

Raw rate refers to number of k's that passed the "classes test". Note that you only test a small number of the 4620 classes. Even classes and clases where factors are divisible by 3,5,7,11 are eliminated before doing any GPU sieving.

Note that in mfaktc the column is called avg. rate and refers to the number of k's after the classes test AND after the CPU sieving.

[aketilander]

Originally Posted by Prime95

That was an easy fix.

Excellent! Thank you for taking your time doing it!

[f11ksx]

Hello everybody,

i have this result with MMFF:
F39 has a factor: 304649306542939328584089601
[TF:87:88:mmff 0.26 mfaktc_barrett89_F32_63gs]
found 1 factor for k*2^44+1 in k range: 10000000000000 to 17592186044415 (88-bit factors) [mmff 0.26 mfaktc_barrett89_F32_63gs]


That is 17 317 308 137 475*2^44+1

but Fermat.exe find no factor.
Any idea ?

[axn]

Originally Posted by f11ksx

Hello everybody,

i have this result with MMFF:
F39 has a factor: 304649306542939328584089601
[TF:87:88:mmff 0.26 mfaktc_barrett89_F32_63gs]
found 1 factor for k*2^44+1 in k range: 10000000000000 to 17592186044415 (88-bit factors) [mmff 0.26 mfaktc_barrett89_F32_63gs]


That is 17 317 308 137 475*2^44+1

but Fermat.exe find no factor.
Any idea ?

It is a composite factor. 304649306542939328584089601 = (3*2^41+1)*(21*2^41+1)

3*2^24+1 divides F38.
21*2^41+1 divides F39.

Hmmm... How come the composite factor divides F39?

[Batalov]

Nah, it's ok; I've seen this with mmff-gfn.
The exit criterion from factoring (repeated squaring) is either -1 modulus or 1 (probably in case that -1 went unnoticed). So, when mod is 1, then it gets obviously repeated forever. A factor (a product of two prime factors that divide two different Fm values) can get through like that. Because of the implementation details, pfgw -gxo will get equally confused (try it!), but it will produce a less misleading answer.

Actually, pfgw is not fooled by this number in -go mode, only in -gxo:

> pfgw -f -gxo -q"17317308137475*2^44+1"
PFGW Version 3.4.6.64BIT.20110307.x86_Dev [GWNUM 26.5]
 
A GF Factor was found, but the base of 12 may not be correct.
17317308137475*2^44+1 is a Factor of xGF(12,3,2)!!!! (0.000000 seconds)
A GF Factor was found, but the base of 12 may not be correct.
17317308137475*2^44+1 is a Factor of xGF(12,4,3)!!!! (0.000000 seconds)
A GF Factor was found, but the base of 12 may not be correct.
17317308137475*2^44+1 is a Factor of xGF(12,8,3)!!!! (0.000000 seconds)
A GF Factor was found, but the base of 12 may not be correct.
17317308137475*2^44+1 is a Factor of xGF(12,9,2)!!!! (0.000000 seconds)
A GF Factor was found, but the base of 12 may not be correct.
17317308137475*2^44+1 is a Factor of xGF(12,9,8)!!!! (0.000000 seconds)
GFN testing completed

[ET_]

Originally Posted by axn

It is a composite factor. 304649306542939328584089601 = (3*2^41+1)*(21*2^41+1)

3*2^24+1 divides F38.
21*2^41+1 divides F39.

Hmmm... How come the composite factor divides F39?

May I suggest the insertion of a test to check if the factor is composite on mmff 0.27?

Luigi

[axn]

Originally Posted by Batalov

Nah, it's ok; I've seen this with mmff-gfn.
The exit criterion from factoring (repeated squaring) is either -1 modulus or 1 (probably in case that -1 went unnoticed).

Gotcha.

[Batalov]

Originally Posted by ET_

May I suggest the insertion of a test to check if the factor is composite on mmff 0.27?

Luigi

Checking for compositeness only (without factoring) is probably fairly cheap to add even using dumnums. Factoring (when the binary representation of k appears very sparse) is another possibility:
(s*2^m+1)*(t*2^m+1) = (s*t*2^m + (s+t))*2^m+1 = k*2^m+1
would be pretty easy to spot (with s and t small, s+t << 2^m, though not necessarily both odd)

Maybe we could add this to mmff 0.28? It is easy to do externally for now.

P.S. Cheap demonstration for this particular k:
> dc
2o 17317308137475p
11111100000000000000000000000000000000000011

[RichD]

I've had to restart my mmff-0.26 run on MMFactor=127 but it doesn't appear to look for a .ckp file even though I have checkpoint turned on in the .ini file.

Is anyone else having this problem?