mersenneforum.org  

Go Back   mersenneforum.org > Prime Search Projects > Proth Prime Search

Reply
 
Thread Tools
Old 2020-01-06, 13:36   #1
David703
 
Oct 2019

17 Posts
Default Question about sieving

Hi, I'm currently using newpgen to sieve a range for proth primes but I suspect the software that primegrid uses (sr2ppsieve, in my case I would use the CUDA version) would be much faster than that. Am I right? If yes, were can I download that program?
David703 is offline   Reply With Quote
Old 2020-01-06, 14:02   #2
rogue
 
rogue's Avatar
 
"Mark"
Apr 2003
Between here and the

10111001100112 Posts
Default

Quote:
Originally Posted by David703 View Post
Hi, I'm currently using newpgen to sieve a range for proth primes but I suspect the software that primegrid uses (sr2ppsieve, in my case I would use the CUDA version) would be much faster than that. Am I right? If yes, were can I download that program?
What range are you sieving? Are you sieving fixed k or fixed n? Just want to see if you are using the optimal software for sieving as newpgen is much slower than many other sieveing programs, depending upon what you are sieving.
rogue is offline   Reply With Quote
Old 2020-01-06, 14:18   #3
David703
 
Oct 2019

17 Posts
Default

Hi! I was thinking to get into prime testing outside big projects (GIMPS and PrimeGrid), so I was just experimenting a little bit with random values.

I thought that the only possible sieving was with fixed n so I was doing n=4156789 and Ks between 75000 and 95000 (as I stated, completely random). What ranges should I sieve with which program? I'm completely new to this and had no idea that the optimal program to use for sieving depended on the range.
David703 is offline   Reply With Quote
Old 2020-01-06, 21:20   #4
rogue
 
rogue's Avatar
 
"Mark"
Apr 2003
Between here and the

5,939 Posts
Default

Quote:
Originally Posted by David703 View Post
Hi! I was thinking to get into prime testing outside big projects (GIMPS and PrimeGrid), so I was just experimenting a little bit with random values.

I thought that the only possible sieving was with fixed n so I was doing n=4156789 and Ks between 75000 and 95000 (as I stated, completely random). What ranges should I sieve with which program? I'm completely new to this and had no idea that the optimal program to use for sieving depended on the range.
My recommendation is to get your feet wet with a smaller project, i.e. one with fewer participants. You will have less software to choose from and can communicate directly with the person maintaining that project. The project maintainer might also give you some ideas for small range to test until you are comfortable with the software.

The simplest ones that quickly come to mind are the Generalied Cullen and Generalized Woodall searches. I call these "simplest" because the form of the prime is easy to identify and have no special symbols. The search spaces are also fairly small compared to other projects so one quickly gets into the Top 5000 prime territory.

Next up would be Carol/Kynea or Multifactorial. These forms are a little harder to understand as they have symbols beyond the +, -, ^, and * operators.

From there you find projects with more participants which means you are more at risk for poaching or searching ranges that have already been searched. This would include the Proth Prime Search, the Riesel Prime Search, and CRUS. The Riesel and Sierpinski forms have a lot of searchers and multiple projects, depending upon their focus. The search space is much larger than most other projects.

For most of the smaller projects you are likely to use a program built upon the mtsieve framework. For full disclosure I wrote mtsieve and have assisted more prime searching projects here or at PrimeGrid than most others. I have not participated on GIMPS and my participation of PrimeGrid projects occurred before PrimeGrid grew to its current size.

Once you have spent some time on smaller projects and have hopefully made some contributions, you should have more confidence to contribute to the larger projects without anyone denigrating any of your work.

Last fiddled with by rogue on 2020-01-06 at 21:20
rogue is offline   Reply With Quote
Old 2020-08-30, 16:21   #5
bur
 
Aug 2020

2×3×5 Posts
Default

Just for fun I wanted to do some manual hunting. To keep the CPUs on Primegrid, I want to do it with GPU only. I appears Proth primes are good candidates since there is both sieving and prime testing software for GPU available.


I want to have a fixed k (in 10^6 range far from PG's range) and sieve for n values around 10^6. Is sr2sieve the best choice?


For primality testing the sieved candidates I want to use proth20, anyone used that before?

Last fiddled with by bur on 2020-08-30 at 16:40
bur is offline   Reply With Quote
Old 2020-08-31, 00:23   #6
rogue
 
rogue's Avatar
 
"Mark"
Apr 2003
Between here and the

5,939 Posts
Default

Quote:
Originally Posted by bur View Post
Just for fun I wanted to do some manual hunting. To keep the CPUs on Primegrid, I want to do it with GPU only. I appears Proth primes are good candidates since there is both sieving and prime testing software for GPU available.

I want to have a fixed k (in 10^6 range far from PG's range) and sieve for n values around 10^6. Is sr2sieve the best choice?

For primality testing the sieved candidates I want to use proth20, anyone used that before?
You would have to test with proth20 to see how well is works. Then you would have to run some of the same tests with llr to see which one is faster.
rogue is offline   Reply With Quote
Old 2020-08-31, 06:59   #7
bur
 
Aug 2020

2×3×5 Posts
Default

Quote:
Then you would have to run some of the same tests with llr to see which one is faster.
Is there anything worthwhile other than LLRCuda?


Do you have any recommendation regarding newpgen vs sr2sieve? Or should I just try both?


Also most Proth searches seem to focus on small k. Not just k < 2^n, but k <<< 2^n. Is there a reason for it, like higher efficiency per number of digits?


And is there anything "special" about k values that are prime? I know there was some activity to find a prime k Cullen/Woodall, but not about Proth primes with k being prime.
bur is offline   Reply With Quote
Old 2020-09-01, 08:44   #8
JeppeSN
 
JeppeSN's Avatar
 
"Jeppe"
Jan 2016
Denmark

101000002 Posts
Default

Quote:
Originally Posted by bur View Post
Also most Proth searches seem to focus on small k. Not just k < 2^n, but k <<< 2^n. Is there a reason for it, like higher efficiency per number of digits?


And is there anything "special" about k values that are prime? I know there was some activity to find a prime k Cullen/Woodall, but not about Proth primes with k being prime.
One reason for doing very tiny k is that they are aesthetically more pleasing. Another reason is that the probability that each prime you find, will divide a Fermat number or a generalized Fermat number (with small base(s)), is higher for low k. The probability is 1/k, heuristically, for each base.

But PrimeGrid is already doing all the low k in its different PPS (Proth Prime Search) flavors (PPS-DIV, PPS, PPSE, PPS-MEGA) and for k=3 in their "321" subproject. So to not conflict with PrimeGrid, in my opinion, you must pick a k over 10'000.

For Proth candidates, there is nothing special about k that are prime (other than, again, aesthetics; many people's favorite numbers are primes).

There is something special about k that are perfect cubes, fourth powers and so on; they admit algebraic factorizations of some candidates. So if your k happens to be of this type, be sure that the sieving software, or other software, removes candidates that have special factorizations.

/JeppeSN
JeppeSN is offline   Reply With Quote
Old 2020-09-01, 13:40   #9
bur
 
Aug 2020

2·3·5 Posts
Default

Thanks, I was planning k ~ 10^6 and maybe also k that are prime.



I have some questions about sieving:



I tried sr2sieve and realized I don't really understand the output. It created a factors.txt which showed the factors and the number they divide found during sieving. But don't I need the opposite, a file that lists all potential candidates? And this file I'll feed to the primality test software? How do I tell sr2sieve to create that file?



Also the readme said sr2sieve only handles factors larger than k, for smaller factors one should use newpgen oder srsieve. I think this isn't optional but highly recommended? Otherwise all numbers divisible by 3 or 5 or other small factors will remain as candidates.


So I would use srsieve to sieve for factors <= k and then sr2sieve for factors > k?
bur is offline   Reply With Quote
Old 2020-09-01, 15:20   #10
VBCurtis
 
VBCurtis's Avatar
 
"Curtis"
Feb 2005
Riverside, CA

22·1,093 Posts
Default

Quote:
Originally Posted by bur View Post
So I would use srsieve to sieve for factors <= k and then sr2sieve for factors > k?
Yep! I usually use srsieve to 100M or 500M, and then sr2sieve. At really tiny factor sizes, writing to screen makes sr2sieve slower than srsieve.

One uses srfile to manipulate the files. srsieve outputs an srsieve.out file. The command "srfile -a srsieve.out" converts this file to the abcd format that sr2sieve uses.

sr2sieve creates factor files only because it is designed to be used across multiple machines- in that use case, one wants to collect all the factor files from the various instances and apply them all to a single input file to remove all the factors. So, again srfile is used to do so:
srfile -k factors.txt sr_{base}.abcd -a

Or, if you're ready for LLR, you'd use -G at the end rather than -a to write a file in format LLR prefers. srfile -h will show you all the available formats.
VBCurtis is offline   Reply With Quote
Old 2020-09-01, 17:19   #11
rogue
 
rogue's Avatar
 
"Mark"
Apr 2003
Between here and the

593910 Posts
Default

If using sr2sieve with a k in that range, make sure that you generate the Legendre tables. That should give it a nice speed boost.
rogue is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Sieving Question __HRB__ Math 1 2019-04-28 05:47
Dumb sieving question fivemack Software 7 2017-11-27 22:48
Line sieving vs. lattice sieving JHansen NFSNET Discussion 9 2010-06-09 19:25
A question on lattice sieving joral Factoring 5 2008-04-03 08:01
Sieving question jasong Sierpinski/Riesel Base 5 9 2007-07-23 00:03

All times are UTC. The time now is 17:06.

Wed Oct 21 17:06:14 UTC 2020 up 41 days, 14:17, 0 users, load averages: 1.78, 1.97, 1.96

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.