mersenneforum.org How do you efficiently sieve for prime 3/4-tuples?
 Register FAQ Search Today's Posts Mark Forums Read

 2012-04-09, 18:36 #12 Puzzle-Peter     Jun 2009 12538 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 Cambridge (GMT/BST) 2×29×101 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-09, 19:23   #14
axn

Jun 2003

7·19·37 Posts

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.
Attached Files

2012-04-09, 19:46   #15
Puzzle-Peter

Jun 2009

683 Posts

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

Last fiddled with by Puzzle-Peter on 2012-04-09 at 19:58

2012-04-10, 09:03   #16
ET_
Banned

"Luigi"
Aug 2002
Team Italia

22·3·401 Posts

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

 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-10, 21:55 #18 Puzzle-Peter     Jun 2009 683 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 = -[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 Last fiddled with by Puzzle-Peter on 2012-04-10 at 21:55
2012-04-10, 22:18   #19
axn

Jun 2003

7·19·37 Posts

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.

2012-04-11, 02:26   #20
axn

Jun 2003

7×19×37 Posts

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.
Attached Files
 triple.pas.txt (7.9 KB, 139 views)

 2012-04-11, 14:57 #21 Puzzle-Peter     Jun 2009 683 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 683 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

 Similar Threads Thread Thread Starter Forum Replies Last Post Stargate38 And now for something completely different 2 2017-04-28 00:08 fivemack Math 27 2015-12-12 18:42 tapion64 GPU Computing 7 2014-04-10 06:15 Unregistered Information & Answers 2 2010-05-25 20:51 Sloth Prime Sierpinski Project 1 2006-05-10 02:02

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

Wed Apr 21 05:11:57 UTC 2021 up 12 days, 23:52, 0 users, load averages: 2.07, 1.91, 1.73