mersenneforum.org  

Go Back   mersenneforum.org > Great Internet Mersenne Prime Search > Software

Reply
 
Thread Tools
Old 2012-04-09, 18:36   #12
Puzzle-Peter
 
Puzzle-Peter's Avatar
 
Jun 2009

12538 Posts
Default

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
Puzzle-Peter is offline   Reply With Quote
Old 2012-04-09, 19:16   #13
henryzz
Just call me Henry
 
henryzz's Avatar
 
"David"
Sep 2007
Cambridge (GMT/BST)

2×29×101 Posts
Default

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.
henryzz is offline   Reply With Quote
Old 2012-04-09, 19:23   #14
axn
 
axn's Avatar
 
Jun 2003

7·19·37 Posts
Default

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
File Type: txt Quad.pas.txt (8.4 KB, 156 views)
axn is online now   Reply With Quote
Old 2012-04-09, 19:46   #15
Puzzle-Peter
 
Puzzle-Peter's Avatar
 
Jun 2009

683 Posts
Default

Quote:
Originally Posted by axn View Post
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
Puzzle-Peter is offline   Reply With Quote
Old 2012-04-10, 09:03   #16
ET_
Banned
 
ET_'s Avatar
 
"Luigi"
Aug 2002
Team Italia

22·3·401 Posts
Default

Quote:
Originally Posted by Puzzle-Peter View Post
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
ET_ is offline   Reply With Quote
Old 2012-04-10, 16:40   #17
smh
 
smh's Avatar
 
"Sander"
Oct 2002
52.345322,5.52471

29·41 Posts
Default

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?
smh is offline   Reply With Quote
Old 2012-04-10, 21:55   #18
Puzzle-Peter
 
Puzzle-Peter's Avatar
 
Jun 2009

683 Posts
Default

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
Puzzle-Peter is offline   Reply With Quote
Old 2012-04-10, 22:18   #19
axn
 
axn's Avatar
 
Jun 2003

7·19·37 Posts
Default

Quote:
Originally Posted by Puzzle-Peter View Post
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 is online now   Reply With Quote
Old 2012-04-11, 02:26   #20
axn
 
axn's Avatar
 
Jun 2003

7×19×37 Posts
Default

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
File Type: txt triple.pas.txt (7.9 KB, 139 views)
axn is online now   Reply With Quote
Old 2012-04-11, 14:57   #21
Puzzle-Peter
 
Puzzle-Peter's Avatar
 
Jun 2009

683 Posts
Default

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 is offline   Reply With Quote
Old 2012-04-14, 06:39   #22
Puzzle-Peter
 
Puzzle-Peter's Avatar
 
Jun 2009

683 Posts
Default

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.
Puzzle-Peter is offline   Reply With Quote
Reply

Thread Tools


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

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

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.