How do you efficiently sieve for prime 3/4-tuples? - Page 2

Puzzle-Peter · 2012-04-09, 18:36

Luigi,

how many candidates do you start with? I'd like to do at least 1e11 k values at a time, but using fermfact the files are way too large.

Peter

henryzz · 2012-04-09, 19:16

I wonder how difficult it would be to add a switch in srsieve that removes all the correct candidates for quads when a factor is found.

axn · 2012-04-09, 19:23

I have adapted my LuckyMinus code to sieve for quadruples [k*2^n-1,+1,+5,+7]. Attached is the source code in Pascal. You'll need freepascal or another pascal compiler to compile the code. If needed, I can post a windows executable. More thorough testing needs to be done. Once the initial sieving is done by the program, you can use NewPGen to take it to higher depths.

Puzzle-Peter · 2012-04-09, 19:46

Quote:

Originally Posted by axn

I have adapted my LuckyMinus code to sieve for quadruples [k*2^n-1,+1,+5,+7]. Attached is the source code in Pascal. You'll need freepascal or another pascal compiler to compile the code. If needed, I can post a windows executable. More thorough testing needs to be done. Once the initial sieving is done by the program, you can use NewPGen to take it to higher depths.

Wow, this is very cool! Thanks a lot! I'll test it but not today - I have to get up early tomorrow...

EDIT: A windows executable (32 bit) would be very much appreciated.

EDIT2: *lol* Of course I couldn't resist. I downloaded freepascal and it compiled nicely ( so no need for a windows executable). Now it's running and I am very curious about timings...

ET_ · 2012-04-10, 09:03

Quote:

Originally Posted by Puzzle-Peter

Luigi,

how many candidates do you start with? I'd like to do at least 1e11 k values at a time, but using fermfact the files are way too large.

Peter

My FermFact files are huge

that's why I used NewPGen format and split results in many files that I later glue together using another C program I wrote.

I usually handle files of tehths of Megabytes (my last work was on N=61000 to 70000, and k=20000 to 30000), that's like starting with about 2.5*10^18 values, that become 3*10^6 after a few seconds of sieving.

Keep in mind that FermFact is best used with N > 10000 and "squared areas", that is about the same number of Ns and ks...

Luigi

smh · 2012-04-10, 16:40

How about running newpgen to 10/50/100M. It will still split the files but won't sieve that long. After that, manually combine the sieve files and start newpgen where you left off?

Puzzle-Peter · 2012-04-10, 21:55

I'm doing single-n searches with lots of k values, meaning 1e13 k's and more. Even when split and sieved to p=1G with NewPGen the resulting file is 1+ GB sieved for quadruples, many times that when only sieved for twins or, even worse, sierpinski primes.

I tried using NewPGen and make it sieve to only 100M and it really does speed up the process by 50% while the files get about twice as large which seems to be a good compromise. So without axn's help this would probably be the way to go.

Now I don't have exact exact timings for axn's code yet, but first tests seem to hint at a 90% reduction in time for a 1T range sieved to p=1G. I don't yet know how it copes with bigger ranges. I'll keep you updated.

Speaking of the code, when I want to use it to sieve for triplets, I think this part

Code:

      { c = +7 ==> x = -[7*t+k] }
      x := t*2; if(x >= n) then x := x - n; {2t}
      x := x+t; if(x >= n) then x := x - n; {3t}
      x := x*2; if(x >= n) then x := x - n; {6t}
      x := x+t; if(x >= n) then x := x - n; {7t}
      x := x+k; if(x >= n) then x := x - n; {7t+k}
      if(x > 0) then x := n-x; { - }
      ndx[i, 4] := x;

must be removed. But is that all that has to be changed? To be honest I simply don't understand large parts of the code...

Thanks again to everybody who's trying to help.

Peter

axn · 2012-04-10, 22:18

Quote:

Originally Posted by Puzzle-Peter

Speaking of the code, when I want to use it to sieve for triplets, I think this part

Code:

      { c = +7 ==> x = -[7*t+k] }
      x := t*2; if(x >= n) then x := x - n; {2t}
      x := x+t; if(x >= n) then x := x - n; {3t}
      x := x*2; if(x >= n) then x := x - n; {6t}
      x := x+t; if(x >= n) then x := x - n; {7t}
      x := x+k; if(x >= n) then x := x - n; {7t+k}
      if(x > 0) then x := n-x; { - }
      ndx[i, 4] := x;

must be removed. But is that all that has to be changed?

Not just that part. When sieving the quad form, we have some additional modular restrictions (compared to sieving the triple form) -- so there is a greater gain in efficiency. You'll see a few "30" being thrown about along the code. These also needs to be adjusted for the triple form. Overall, the efficiency improvement compared to NewPGen isn't that great when sieving the triple form (maybe 3x). If you're interested, I can build a triple sieve -- but it'll have to wait till the weekend.

axn · 2012-04-11, 02:26

That went faster than expected. Here's the triple version. I've modified it to accept the k range in G rather than T. It's probably between 2x and 3x faster than NewPGen.

Puzzle-Peter · 2012-04-11, 14:57

Thanks for making the triple version! I knew there would be some hidden subtleties to modify... T ranges would have been ok as any triple large enough to make Chris Caldwells TOP20 needs a search space of several T's except you're very lucky. But that's not important and I can change this myself.

As for the quad, I did a 1T range with both your code and NewPGen. The files matched perfectly and my 10fold speedup estimate (based on the first few minutes) turned out to be quite accurate. Great work! I'll play around with different sievesize settings and then test the triple version.

Thanks again!
Peter

Puzzle-Peter · 2012-04-14, 06:39

Wow, switching to a 12core machine I can do 600T for quads in less than 4 days. Chunks of 50T (resulting in 2GB files each) is about the max that NewPGen is able to digest. This is great!

I see a slowdown when running on several cores at once. It's probably due to having Sievesize>L2Cache which was fastest on 1 core. I'll try if Sievesize<L2Cache is better for using all cores.

2012-04-10, 21:55	#18
Puzzle-Peter Jun 2009 2²·5²·7 Posts	I'm doing single-n searches with lots of k values, meaning 1e13 k's and more. Even when split and sieved to p=1G with NewPGen the resulting file is 1+ GB sieved for quadruples, many times that when only sieved for twins or, even worse, sierpinski primes. I tried using NewPGen and make it sieve to only 100M and it really does speed up the process by 50% while the files get about twice as large which seems to be a good compromise. So without axn's help this would probably be the way to go. Now I don't have exact exact timings for axn's code yet, but first tests seem to hint at a 90% reduction in time for a 1T range sieved to p=1G. I don't yet know how it copes with bigger ranges. I'll keep you updated. Speaking of the code, when I want to use it to sieve for triplets, I think this part Code: { c = +7 ==> x = -[7t+k] } x := t2; if(x >= n) then x := x - n; {2t} x := x+t; if(x >= n) then x := x - n; {3t} x := x2; if(x >= n) then x := x - n; {6t} x := x+t; if(x >= n) then x := x - n; {7t} x := x+k; if(x >= n) then x := x - n; {7t+k} if(x > 0) then x := n-x; { - } ndx[i, 4] := x; must be removed. But is that all that has to be changed? To be honest I simply don't understand large parts of the code... Thanks again to everybody who's trying to help. Peter Last fiddled with by Puzzle-Peter on 2012-04-10 at 21:55*

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
How/Where to get Jens Kruse Andersen's prime constellation sieve?	Stargate38	And now for something completely different	2	2017-04-28 00:08
Efficiently finding a linear progression in data	fivemack	Math	27	2015-12-12 18:42
GPU Prime Sieve	tapion64	GPU Computing	7	2014-04-10 06:15
Sieve depth vs. prime probability	Unregistered	Information & Answers	2	2010-05-25 20:51
Prime in Riesel Sieve Project	Sloth	Prime Sierpinski Project	1	2006-05-10 02:02

2012-04-09, 18:36	#12
Puzzle-Peter Jun 2009 2BC₁₆ Posts	Luigi, how many candidates do you start with? I'd like to do at least 1e11 k values at a time, but using fermfact the files are way too large. Peter

2012-04-09, 19:16	#13
henryzz Just call me Henry "David" Sep 2007 Liverpool (GMT/BST) 2²·1,553 Posts	I wonder how difficult it would be to add a switch in srsieve that removes all the correct candidates for quads when a factor is found.

2012-04-10, 16:40	#17
smh "Sander" Oct 2002 52.345322,5.52471 29·41 Posts	How about running newpgen to 10/50/100M. It will still split the files but won't sieve that long. After that, manually combine the sieve files and start newpgen where you left off?

2012-04-11, 14:57	#21
Puzzle-Peter Jun 2009 2²·5²·7 Posts	Thanks for making the triple version! I knew there would be some hidden subtleties to modify... T ranges would have been ok as any triple large enough to make Chris Caldwells TOP20 needs a search space of several T's except you're very lucky. But that's not important and I can change this myself. As for the quad, I did a 1T range with both your code and NewPGen. The files matched perfectly and my 10fold speedup estimate (based on the first few minutes) turned out to be quite accurate. Great work! I'll play around with different sievesize settings and then test the triple version. Thanks again! Peter

2012-04-14, 06:39	#22
Puzzle-Peter Jun 2009 2²·5²·7 Posts	Wow, switching to a 12core machine I can do 600T for quads in less than 4 days. Chunks of 50T (resulting in 2GB files each) is about the max that NewPGen is able to digest. This is great! I see a slowdown when running on several cores at once. It's probably due to having Sievesize>L2Cache which was fastest on 1 core. I'll try if Sievesize<L2Cache is better for using all cores.