Join PrimeGrid
Returning Participants
Community
Leader Boards
Results
Other
drummerslowrise

Message boards :
Proth Prime Search :
How can we beat GIMPS
Author 
Message 

All primes end in 1 3 7 9. Is there some optimization PrimeGrid can do to reduce the cost function so that we are not checking "obvious" non primes? Geeeze!!
 


Sieve already does remove a lot of candidates relatively quickly and easily.  

Dave Send message
Joined: 13 Feb 12 Posts: 2526 ID: 130544 Credit: 757,380,009 RAC: 0

Best thing I would think is to try manual sieving for n=22.  


All primes end in 1 3 7 9. Is there some optimization PrimeGrid can do to reduce the cost function so that we are not checking "obvious" non primes? Geeeze!!
Primegrid use sieve depth as we, as individual will never reach. So it reduce "checking" of "non"obvious non primes alot!
I will give you example: I now run my small project
My sieve ( I need to do LLR) has 42400 candidates. If I have sieve depth from Primegrid I will have to check only 33000 candidates.
Second , I sow you are new here, you are not find any prime. Primegrid is not for non patient persons.
And last, does you join for finding primes or for collecting points and badges?
I wish you luck, what ever your motive is!
____________
271643232^^{131072}+1 GENERALIZED FERMAT :)
93*10^^{1029523}1 REPDIGIT PRIME
31*332^^{367560}+1 CRUS PRIME
Proud member of team Aggie The Pew. Go Aggie!  

Michael GoetzVolunteer moderator Project administrator Project scientist
Send message
Joined: 21 Jan 10 Posts: 12669 ID: 53948 Credit: 184,159,862 RAC: 18

Best thing I would think is to try manual sieving for n=22.
GIMPS is currently searching numbers larger than anything PrimeGrid is searching, including n=22. Sieving n=22 will not help.
____________
Please do not PM me with support questions. Ask on the forums instead. Thank you!
My lucky number is 75898^{524288}+1  


All primes end in 1 3 7 9.
When you sieve to p=2, you remove all candidates ending in 0,2,4,6,8. And when you sieve to p=5, you remove candidates ending in 5 as well.
/JeppeSN  

RafaelVolunteer tester
Send message
Joined: 22 Oct 14 Posts: 847 ID: 370496 Credit: 286,652,912 RAC: 0

GIMPS is currently searching numbers larger than anything PrimeGrid is searching, including n=22. Sieving n=22 will not help.
The "GFN22WR" dream (an analogy to GFN17MEGA) would be much less of a distant dream if n=22 was properly sieved, don't you agree?
Or we could go crazy and start sieving n=23.
Not that any of those seem really likely to me, at least not within the spam of the next few years. But who knows, maybe in the future...  

Michael GoetzVolunteer moderator Project administrator Project scientist
Send message
Joined: 21 Jan 10 Posts: 12669 ID: 53948 Credit: 184,159,862 RAC: 18

GIMPS is currently searching numbers larger than anything PrimeGrid is searching, including n=22. Sieving n=22 will not help.
The "GFN22WR" dream (an analogy to GFN17MEGA) would be much less of a distant dream if n=22 was properly sieved, don't you agree?
Or we could go crazy and start sieving n=23.
Not that any of those seem really likely to me, at least not within the spam of the next few years. But who knows, maybe in the future...
The "dream" of finding the world's largest known prime with the GFN22 search ended when the most recent Mersenne prime was found by GIMPS. That latest Mersenne is, and always will be, beyond the range of the GFN22 search due to the fact that the GFN searches increment B while the Mersenne search increments N. No amount of sieving will change that. Besides, 22 is exceptionally well sieved to a much higher level than the other ranges.
"Going crazy" and sieving/searching n=23 is a possibility, but the odds are even worse for n=23 than they were for n=22.
____________
Please do not PM me with support questions. Ask on the forums instead. Thank you!
My lucky number is 75898^{524288}+1  


All primes end in 1 3 7 9. Is there some optimization PrimeGrid can do to reduce the cost function so that we are not checking "obvious" non primes? Geeeze!!
Primegrid use sieve depth as we, as individual will never reach. So it reduce "checking" of "non"obvious non primes alot!
I will give you example: I now run my small project
My sieve ( I need to do LLR) has 42400 candidates. If I have sieve depth from Primegrid I will have to check only 33000 candidates.
Second , I sow you are new here, you are not find any prime. Primegrid is not for non patient persons.
And last, does you join for finding primes or for collecting points and badges?
I wish you luck, what ever your motive is!
Very sorry to give you impression that I am impatient, I am not. I usually run Rosetta in which tasks take longer than Proth. I'm interested in finding Primes. To me number crucnching should be much faster than Protein Folding... which it is. I just thought number crunching would be alot faster. But I am okay with that. I hope my perceived impatience will not bother you. :)
 

RafaelVolunteer tester
Send message
Joined: 22 Oct 14 Posts: 847 ID: 370496 Credit: 286,652,912 RAC: 0

Very sorry to give you impression that I am impatient, I am not. I usually run Rosetta in which tasks take longer than Proth. I'm interested in finding Primes. To me number crucnching should be much faster than Protein Folding... which it is. I just thought number crunching would be alot faster. But I am okay with that. I hope my perceived impatience will not bother you. :)
Depends on the type of number being crunch. The PPS searchs are the fastest ones available at PrimeGrid, the other one being SGS.
Try something like Cullen or Seventeen or Bust, and you'll see just how lengthy prime crunching can be...  


I'm good. I'll stay with Proth.  

JimBVolunteer moderator Project administrator Project developer Send message
Joined: 4 Aug 11 Posts: 871 ID: 107307 Credit: 832,273,633 RAC: 0

I figure maybe I should post an explanation of all this. I remember how incomprehensible it all was when I first joined.
For all the Prime Proth Search projects (PPS, PPSE, PPS Mega) we're looking at candidates (potential primes) of the form k*2^n+1 or to make it easier to see which operation is performed first: (k*(2^n))+1
* means multiplication where (at least when I was a kid) x was used.
3*5 = 15, 7*8 = 56, etc.
^ means exponentiation  raising a number to a power.
2^5 is 32 because 32 = 2*2*2*2*2  two multiplied by itself five times.
k and n are always integers (whole numbers) and always greater than zero.
k is an odd number between 5 and 1199 (for PPS)
k is an odd number between 1201 and 9999 (for PPSE)
k is an odd number between 5 and 399 (for PPS MEGA)
k starts at 5 rather than 3 because all k=3 are tested in the 321 subproject.
PPS MEGA are really just PPS candidates that happen to have over 1 million digits because they have a larger n. k is only up to 399 so far because we don't yet need more candidates (the next batch will be k=401499). When PPS reaches PPS MEGA territory we'll skip all the candidates already tested by PPS MEGA and at that time PPS MEGA will either change or end.
Why is k always odd? Let's say we're interested in 6*2^5+1. 6 = 2*3 and we could also write this candidate as 3*2^6+1. Either way the value is 193 (which is prime). By sticking to odd k values, we make sure that every candidate is tested only once. With an odd k we know that every combination of k and n create a unique candidate that isn't repeated anywhere else.
n started at 1 or 2, can be both odd or even, and just keeps getting larger.
So we're multiplying an odd number by an even number. That result is always even. We're then adding one, which means the candidate is always odd  never divisible by 2.
Before we ever think of testing a candidate for primality, we do sieving. You can think of sieving as dividing every candidate by some number. This number, called p, starts at 3 and ideally is always a prime number. Trying to divide by nonprimes is just a waste of time. Even though I said "divide", we're really not interested in the answer (the quotient). We're just interested in the remainder. If the remainder is zero, the candidate is evenly divisible by whatever p value we're using. A prime is only divisible by 1 and itself, so any candidate where we have found some factor p is immediately eliminated. It will never have a primality test done on it because we've proven beyond a doubt that it is not prime.
As we sieve, the p value gets larger and larger. Small primes like 3, 5, 7, 11, 13, etc are eliminated immediately, long before sieving ever gets put on PrimeGrid. Early sieving generates so many factors so quickly that until recently we didn't even bother keeping the factors. It's faster to just run the sieving again (if it was ever needed) than to store gigabytes of factors. So early sieving produces what we call sieve files. That's a list of all the candidates that have not yet been eliminated.
By the way, while it takes time to test candidates against potential factors, verifying factors is very fast and easy. Each and every factor produced by sieving, no matter which project it's for, is tested at least twice to make sure it's really valid. It takes only a few minutes to test all the PPS Sieving factors produced in a month, so there's no reason not to test and retest them.
Early sieving is done on the computer(s) of someone behind the scenes at PrimeGrid. At one time Lennart did that, now I do. I will have sieved to p=10T (that's ten trillion or 10,000,000,000,000) before the PrimeGrid community starts further sieving. So any number that has a factor less then 10T has already been eliminated. While that might seem like a large number, it's really not. We sieve until it takes less time to primality test every remaining candidate than it does to eliminate them by further sieving. You can think of that as candidates fully tested per day vs candidates sieved out per day. When the first value is greater than the second value, we're done sieving.
Because we don't want to sieve an endless number of candidates at once, we sieve ranges of n. Initially I believe we sieved n=1100K or 1500K. These days for PPS projects we sieve three million n values at a time. Right now on BOINC we're sieving n=6M9M which means 6,000,0008,999,999. In the manual sieving we're doing n=9M12M. You'll sometimes see that written as 9M <= n < 12M. For n values below 6M, we hit the optimal sieving level and don't currently sieve any further. For n under 3M we sieved to 100P. For n=3M6M that optimal p value was 400P. P = Peta = 10^15, so 400P = 400,000,000,000,000,000. We sieved 3M6M higher because those candidates are larger and take much more time for primality testing. So it was worth sieving for much longer. At some point when we've hit the optimal sieving level for n=6M9M, we'll shift 9M12M to BOINC and (probably) start manual sieving on n=12M15M. But in truth, we won't be primality testing those in my lifetime unless some new muchfaster code is invented. Right now, BOINC PPS sieving is around p=172P as you can see at http://www.primegrid.com/stats_pps_sieve.php. Any factor counts you see there are for factors found in the last hour. Once an hour all factors are swept into a file that's stored on the server (and automatically downloaded by me five minutes later). Those factors are kept forever.
You might wonder why we talk about PPS, PPSE and PPS Mega in the LLR projects while the sieving is sometimes called PPR Sieving. That's because we also sieve for candidates in the form of k*2^n1. Those candidates are called Riesel numbers and it takes very little extra time to generate them. While we don't really use that sieving here except on the 321 project and the PRPNet k=27 and k=121 projects, we do make those sieves available for people outside of PrimeGrid. You can see all the Riesel sieves at http://www.primegrid.com/sieving/rsp. If you're so curious that you have to download one of them, please choose one of the smaller files in the bottom section. We get charged for every byte of download. Many of those candidates have already been tested, so please don't waste your time unless you first read the Riesel Prime Search forum on mersenneforum.org.
As you can see on the above download page, we produce one sieve file per 1M of n. Plus there are separate sieves for +1 (PPS) and 1 (RSP). That's because those sieves are so large. Factors produced are applied to all six sieve files covering that n range. Any given factor only affects one sieve file at most, of course.
Finally, PPS sieving is what's called datless sieving. Every candidate is tested without regard to any existing sieve file. On the GPU, this is actually much faster than only testing the remaining candidates. So a lot of factors are found for candidates that have already been eliminated. There's no statistics chart that shows the actual sieve removal rate for PPS sieving, but about 2223% of factors found result in removals from the sieve. That's taken into account when we determine the optimal sieving point, as only sieve removals matter.
Eventually when we're done sieving, those sieve files become the lists of candidates loaded into the BOINC system to be LLR tested for primality. So you can see that we've eliminated the vast majority of the candidates (1/3 of them are divisible by 3) and we're primality testing the minimum practical number of them.  


Very sorry to give you impression that I am impatient, I am not. I usually run Rosetta in which tasks take longer than Proth. I'm interested in finding Primes. To me number crucnching should be much faster than Protein Folding... which it is. I just thought number crunching would be alot faster. But I am okay with that. I hope my perceived impatience will not bother you. :)
No, I am just a member of Primegrid as you are!
Also I temporary left Primegrid ( you can see on my RAC) because I wont to search outside "range" that Primegrid tested.
And that is all. I wish that you find many primes :)
____________
271643232^^{131072}+1 GENERALIZED FERMAT :)
93*10^^{1029523}1 REPDIGIT PRIME
31*332^^{367560}+1 CRUS PRIME
Proud member of team Aggie The Pew. Go Aggie!  

Message boards :
Proth Prime Search :
How can we beat GIMPS 