mersenneforum.org  

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

Reply
 
Thread Tools
Old 2012-04-08, 19:04   #1
Puzzle-Peter
 
Puzzle-Peter's Avatar
 
Jun 2009

22×132 Posts
Default How do you efficiently sieve for prime 3/4-tuples?

Hey folks,

after finding a record prime quadruple, I'd like to stay in the field of triples and quadruples a bit longer. But the sieving takes a lot of time. I'm looking for a better way to do it.

My problem is that NewPGen splits the sieving range into bits of 485MB, takes them to p=1G and combines them. After combining it's fine, but to get to p=1G takes many days for a k-range of 10T (which is only a small part of the range I expect I'll have to search). Interestingly, for the combined file NewPGen can address much more than 485MB. I tried to contact Paul Jobling without success. Two mail addresses bounced, the third gave no reaction at all.

So I tried to work around this. I wanted to find a way to quickly create an input file for NewPGen to start from. But all sr(x)sieve versions seem to be for not very many k values but lots of n values. I thought about creating a file which is not sieved at all using a simple awk script but those files would get way too large. APsieve is also limited to rather small chunks.

Any suggestions about doing this more efficiently? All I need is a way to speed up the very first stage of sieving but I have run out of ideas.

Thanks
Peter
Puzzle-Peter is offline   Reply With Quote
Old 2012-04-08, 19:19   #2
firejuggler
 
firejuggler's Avatar
 
Apr 2010
Over the rainbow

13·191 Posts
Default

Wich form are they? Base 2? if it's base 2 you can use fermfact. it's a siever, so you can sieve the +1 side , specifing kmin and kmax as well as nmin and nmax.

Last fiddled with by firejuggler on 2012-04-08 at 19:43
firejuggler is offline   Reply With Quote
Old 2012-04-08, 19:22   #3
Puzzle-Peter
 
Puzzle-Peter's Avatar
 
Jun 2009

22·132 Posts
Default

Sorry, forgot to mention that. I'm looking at k*2^n -1, +1, +5, (and +7 for quadruples).

I am not familiar with fermfact, I'll take a look at it. Thanks!
Puzzle-Peter is offline   Reply With Quote
Old 2012-04-08, 19:26   #4
firejuggler
 
firejuggler's Avatar
 
Apr 2010
Over the rainbow

46638 Posts
Default

It's originally designed to find fermat factor, which are k*2^n+1. Since those prime are included in your tuple, that could work.
Edit : it's availlable on fermatsearch.org

Last fiddled with by firejuggler on 2012-04-08 at 19:32
firejuggler is offline   Reply With Quote
Old 2012-04-08, 19:48   #5
Puzzle-Peter
 
Puzzle-Peter's Avatar
 
Jun 2009

22×132 Posts
Default

OK, I tried a small batch (k-range of 1e10 sieved to 1G) and I got an ABCD file of 764MB. Sieving only one form of a tuple does not get rid of the candidates very quickly.

I'll do some more testing but I am afraid this might not work as nicely as I hoped. Thanks anyway!

EDIT: It seems the range of k is limited to about 5e10. Let's see how far that gets us in a timely manner...

Last fiddled with by Puzzle-Peter on 2012-04-08 at 19:52
Puzzle-Peter is offline   Reply With Quote
Old 2012-04-09, 08:55   #6
Puzzle-Peter
 
Puzzle-Peter's Avatar
 
Jun 2009

2A416 Posts
Default

I'm afraid this won't work. Sieving the +1 form only does not remove enough candidates, so I'm getting files in the 20+ GB size range when trying to use the largest possible k range.

Maybe a twin sieve could do the trick, but those I know are rather limited also. If only NewPGen could be forced to take larger bites at once...
Puzzle-Peter is offline   Reply With Quote
Old 2012-04-09, 10:34   #7
ET_
Banned
 
ET_'s Avatar
 
"Luigi"
Aug 2002
Team Italia

112448 Posts
Default

Did you try ppsieve instead?

Luigi
ET_ is offline   Reply With Quote
Old 2012-04-09, 16:18   #8
Puzzle-Peter
 
Puzzle-Peter's Avatar
 
Jun 2009

22×132 Posts
Default

Quote:
Originally Posted by ET_ View Post
Did you try ppsieve instead?

Luigi
No. It didn't come to mind even though I think I have used it some time in the past. I'll have a look at it. Thanks for the suggestion!
Puzzle-Peter is offline   Reply With Quote
Old 2012-04-09, 16:27   #9
firejuggler
 
firejuggler's Avatar
 
Apr 2010
Over the rainbow

46638 Posts
Default

I'm really sorry it didn't work out with fermfact... well ppsieve will remove from +1 and -1 side. If i remember right there is a version working with cuda.might seep up the process.
firejuggler is offline   Reply With Quote
Old 2012-04-09, 16:30   #10
Puzzle-Peter
 
Puzzle-Peter's Avatar
 
Jun 2009

22×132 Posts
Default

ppsieve does not seem to work as it does not write a candidate file, only a factor file. Plus it requires kmax < pmin so it can't be used to start a sieve.
Puzzle-Peter is offline   Reply With Quote
Old 2012-04-09, 18:23   #11
ET_
Banned
 
ET_'s Avatar
 
"Luigi"
Aug 2002
Team Italia

112448 Posts
Default

Quote:
Originally Posted by Puzzle-Peter View Post
ppsieve does not seem to work as it does not write a candidate file, only a factor file. Plus it requires kmax < pmin so it can't be used to start a sieve.
I'm using ppsieve for presieving Fermat candidates. I start with fermFact up ro 600G/1T (using NewPGen format), cat all results files into one, then switch to ppsieve.

I also wrote a short program to extract all factors from the master file and recreate a new candidates file without the found factors.

Luigi
ET_ 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 02:38.

Sat Dec 5 02:38:09 UTC 2020 up 1 day, 22:49, 0 users, load averages: 1.99, 1.59, 1.49

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, 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.