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

Batalov · 2012-12-13, 11:43

~175

ET_ · 2012-12-13, 12:31

Quote:

Originally Posted by Batalov

~175

firejuggler · 2012-12-13, 13:11

and still "limited" to 188 bits tf?

Prime95 · 2012-12-13, 16:47

Quote:

Originally Posted by flashjh

Edit2: It's only the mfaktc_barrett152_F96_127gs kernel that fails

Thanks for the QA I was too lazy to do.

I've uploaded the fix.

Prime95 · 2012-12-13, 18:22

Quote:

Originally Posted by firejuggler

and still "limited" to 188 bits tf?

220 is the new limit on factor size

Batalov · 2012-12-13, 23:00

In the new high range N~=170, the existing search limit was k=6e12 (>2^42), so mmff-0.27 cannot contribute to the range of N>=178 (because f would be > 2^220), but for the other values below 178, I currently have reached these limits (in e12 units):

Code:

k*2^170+1       6       70.368744177663
k*2^171+1       6       70.368744177663
k*2^172+1       6       70.368744177663
k*2^173+1       6       70.368744177663 will max out at next bit
k*2^174+1       6       70.368744177663e12 (maxed out)
k*2^175+1       6       35.184372088831e12 (maxed out)
k*2^176+1       6       17.592186044415e12 (maxed out)
k*2^177+1       6       8.796093022207e12 (maxed out)

(and I was able to finish the 140<=N<=149 ancient reservation comfortably)

I will however finish those 174<=N<=179 leftovers conventionally (srsieve|newpgen + pfgw|llr sort of thing).

When 180<=N<=199 k-limit was raised to 40e12, my motivation to continue the code extension significantly lessened (k~=6e12 was rather promising; sadly I didn't get lucky there). There is a lot of speed difference between N~=180 and N~=40. When I search for the new candidate ranges, I integrate probablilities (weighted by speed of computation); roughly speaking, k*N^2 is a reasonable estimate.

flashjh · 2012-12-15, 15:31

Quote:

Originally Posted by Prime95

Thanks for the QA I was too lazy to do.

I've uploaded the fix.

Newest mmff27 for Windows 32 and 64 attached.

CUDA 4.2 dll files are here, if you need them. Just put them in the mmff directory.

See here for an example worktodo to use for testing.

Can a mod delete post 295?

henryzz · 2012-12-24, 13:35

Am I correct in thinking that currently mmff/mmf-gfn follows the following procedure?

Sieves a range of k upto the optimal level on the gpu
Tests whether this number is a factor of any of the possible numbers.

Everything is also limited to 220-bits right?

What is the approximate sieve depth reached? How many candidates can be checked a second(excluding the sieving)? What proportion of candidates are actually prime?
How long would it take the gpu to do a prp test on a candidate before using the candidate?

I realize these answers will change with the size k and n. I am basically thinking about near to worst case scenarios(guessing large n with k meaning factor candidates are near 220-bits). I am wondering whether adding a prp test before using a candidate or adding more factoring methods(rho, ecm, fermat) would be a sensible idea.

Batalov · 2012-12-24, 20:44

Quote:

Originally Posted by henryzz

I am wondering whether adding a prp test before using a candidate or adding more factoring methods(rho, ecm, fermat) would be a sensible idea.

Fermat divisibility test takes the same time as a prp test (a bit faster, really).
More factoring methods could possibly help if they are tiny (will fit in GPU code) and faster than the main test.

Adding a prp test after finding a divisor was discussed - but because it is all too easy to do with external tools it wasn't high priority. It is very easy to add to the validator routine (not GPU code).

henryzz · 2012-12-24, 21:35

Quote:

Originally Posted by Batalov

Fermat divisibility test takes the same time as a prp test (a bit faster, really).
More factoring methods could possibly help if they are tiny (will fit in GPU code) and faster than the main test.

Adding a prp test after finding a divisor was discussed - but because it is all too easy to do with external tools it wasn't high priority. It is very easy to add to the validator routine (not GPU code).

Ok thanks

Bdot · 2013-07-03, 23:00

I discovered a bug in mfakto/mfaktc (http://mersenneforum.org/showpost.ph...&postcount=852) when GPUSieveProcessSize=24.

I have not used mmff so far--Is that a valid configuration for mmff? If so, then there's a chance of skipping some FCs during the test, if the code is the same as mfakto and mfaktc.

2012-12-13, 13:11	#300
firejuggler Apr 2010 Over the rainbow 2³×5²×13 Posts	and still "limited" to 188 bits tf? Last fiddled with by firejuggler on 2012-12-13 at 13:14

2012-12-13, 23:00	#303
Batalov "Serge" Mar 2008 Phi(4,2^7658614+1)/2 3⁶×13 Posts	In the new high range N~=170, the existing search limit was k=6e12 (>2^42), so mmff-0.27 cannot contribute to the range of N>=178 (because f would be > 2^220), but for the other values below 178, I currently have reached these limits (in e12 units): Code: k2^170+1 6 70.368744177663 k2^171+1 6 70.368744177663 k2^172+1 6 70.368744177663 k2^173+1 6 70.368744177663 will max out at next bit k2^174+1 6 70.368744177663e12 (maxed out) k2^175+1 6 35.184372088831e12 (maxed out) k2^176+1 6 17.592186044415e12 (maxed out) k2^177+1 6 8.796093022207e12 (maxed out) (and I was able to finish the 140<=N<=149 ancient reservation comfortably) I will however finish those 174<=N<=179 leftovers conventionally (srsieve\|newpgen + pfgw\|llr sort of thing). When 180<=N<=199 k-limit was raised to 40e12, my motivation to continue the code extension significantly lessened (k~=6e12 was rather promising; sadly I didn't get lucky there). There is a lot of speed difference between N~=180 and N~=40. When I search for the new candidate ranges, I integrate probablilities (weighted by speed of computation); roughly speaking, kN^2 is a reasonable estimate. Last fiddled with by Batalov on 2012-12-13 at 23:11*

2012-12-24, 13:35	#305
henryzz Just call me Henry "David" Sep 2007 Cambridge (GMT/BST) 2³×3×5×7² Posts	Am I correct in thinking that currently mmff/mmf-gfn follows the following procedure? Sieves a range of k upto the optimal level on the gpu Tests whether this number is a factor of any of the possible numbers. Everything is also limited to 220-bits right? What is the approximate sieve depth reached? How many candidates can be checked a second(excluding the sieving)? What proportion of candidates are actually prime? How long would it take the gpu to do a prp test on a candidate before using the candidate? I realize these answers will change with the size k and n. I am basically thinking about near to worst case scenarios(guessing large n with k meaning factor candidates are near 220-bits). I am wondering whether adding a prp test before using a candidate or adding more factoring methods(rho, ecm, fermat) would be a sensible idea.

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
Mersenne trial division implementation	mathPuzzles	Math	8	2017-04-21 07:21
trial division over a factor base	Peter Hackman	Factoring	7	2009-10-26 18:27
P95 trial division strategy	SPWorley	Math	8	2009-08-24 23:26
Trial division software for Mersenne	SPWorley	Factoring	7	2009-08-16 00:23
Need GMP trial-division timings	ewmayer	Factoring	7	2008-12-11 22:12

2012-12-13, 11:43	#298
Batalov "Serge" Mar 2008 Phi(4,2^7658614+1)/2 3⁶×13 Posts	~175

2013-07-03, 23:00	#308
Bdot Nov 2010 Germany 255₁₆ Posts	I discovered a bug in mfakto/mfaktc (http://mersenneforum.org/showpost.ph...&postcount=852) when GPUSieveProcessSize=24. I have not used mmff so far--Is that a valid configuration for mmff? If so, then there's a chance of skipping some FCs during the test, if the code is the same as mfakto and mfaktc.