Join PrimeGrid
Returning Participants
Community
Leader Boards
Results
Other
drummers-lowrise
|
Message boards :
General discussion :
Prime Rank question
| Author |
Message |
|---|
|
|
|
On the front page the Prime Rank for the project Generalized Fermat Prime Search (n=22) is listed as 2. Does this mean that there is no way that this project can produce the largest prime yet to be discovered by humans?
I was told that PrimeGrid is a more ambitious project than GIMPS and that we had projects that would discover primes that way larger than anything that GIMPS has produced. Is this not true?
edit: Also, what about the projects that don't have a number in the Prime Rank column, like the Proth Prime Search (sieve)? I would assume that this project is searching for primes (duh), but it doesn't have a rank. Does that mean it would find the largest ever discovered prime? | |
|
 RafaelVolunteer tester
Send message
Joined: 22 Oct 14
Posts: 906
ID: 370496
Credit: 479,176,653
RAC: 206,025
                   
|
On the front page the Prime Rank for the project Generalized Fermat Prime Search (n=22) is listed as 2. Does this mean that there is no way that this project can produce the largest prime yet to be discovered by humans?
Depends on the way you want to look at it. If we keep going sequentially, no, we can't get the world's largest prime, unless GIMPS fails to find a prime for the next, say, 20 years AND there happens to be a prime on the low end of the n=22 spectrum.
Now, we could do a "n=22 WR" project and start a search at a higher B. We do that for n=17, there's the MEGA version which produces larger primes than the regular one. However, that would still rely on GIMPS not finding any primes and there being a nice B in the low end of the spectrum; we could be looking at the next 50 years without a prime on n=22, for example.
And before you ask, a potential n=23, while it would be able to produce a WR prime, it would be even less likely to produce a prime in the first place, so it's not gonna happen either (at least not in a foreseeable future).
So while it's not technically impossible, we can pretty much approximate that PrimeGrid isn't getting WR primes.
I was told that PrimeGrid is a more ambitious project than GIMPS and that we had projects that would discover primes that way larger than anything that GIMPS has produced. Is this not true?
More ambitious? Yes. We aim to prove different sorts of conjectures through brute force, as well as finding lots of non Mersenne primes. But way larger than GIMPS? Not at all.
edit: Also, what about the projects that don't have a number in the Prime Rank column, like the Proth Prime Search (sieve)? I would assume that this project is searching for primes (duh), but it doesn't have a rank. Does that mean it would find the largest ever discovered prime?
Sieve projects will NEVER find primes. That's why they don't have a rank. In fact, it's actually doing the opposite: it's finding factors and proving numbers to be composites, not primes.
The reason we do so is because, up to a point, sieving can remove candidates a lot faster than prime testing. We quickly remove numbers by proving that they aren't prime, through sieving. As you sieve deeper and deeper, the removal rate becomes slower and slower, up until a certain point where it turns out to be faster to primality test rather than sieve; we call that optimal sieve depth, where we stop sieving and do only primality test with a given set of numbers. | |
|
JimB Honorary cruncher
Send message
Joined: 4 Aug 11
Posts: 918
ID: 107307
Credit: 977,945,376
RAC: 45
               
|
|
http://www.primegrid.com/forum_thread.php?id=6837&nowrap=true#95415 | |
|
|
|
|
Thanks! | |
|
compositeVolunteer tester
Send message
Joined: 16 Feb 10
Posts: 1022
ID: 55391
Credit: 887,943,190
RAC: 142,031
                 
|
And before you ask, a potential n=23, while it would be able to produce a WR prime, it would be even less likely to produce a prime in the first place
Among the various forms tested for primality at PG, GFN is used for finding a WR prime. Is that because it has the fastest tests at WR size? If so, is that because the exponent is the smallest, or because the density of prime candidates after seiving is highest, or because the test has the fastest implementation (GPU)?
| |
|
Michael GoetzVolunteer moderator
Project administrator
Send message
Joined: 21 Jan 10
Posts: 13804
ID: 53948
Credit: 345,369,032
RAC: 4,797
            
|
And before you ask, a potential n=23, while it would be able to produce a WR prime, it would be even less likely to produce a prime in the first place
Among the various forms tested for primality at PG, GFN is used for finding a WR prime. Is that because it has the fastest tests at WR size? If so, is that because the exponent is the smallest, or because the density of prime candidates after seiving is highest, or because the test has the fastest implementation (GPU)?
It's not used to test for WR primes. It used to be used to be test for WR primes.
That detail aside, your last possibility (implimentation speed) is the correct answer. Only two types of numbers are being tested that are at world record levels, or near world record levels: Mersenne numbers, and generalized Fermat numbers. The reason for both is the same: they're able to be tested relatively quickly.
Mersenne numbers (tested by GIMPS) are fast because they're the easiest to test and the algorithm to test them is very fast.
Generalized Fermat numbers are fast because not only is Yves' Genefer algorithm very fast, but it works exceptionally well on GPUs. Please note that some types of computation lend themselves better to parallel processing than others. Genefer is one of the ones that does.
____________
My lucky number is 75898524288+1 | |
|
RafaelVolunteer tester
Send message
Joined: 22 Oct 14
Posts: 906
ID: 370496
Credit: 479,176,653
RAC: 206,025
|
[or because the density of prime candidates after seiving is highest
Unfortunately, GFN ranges aren't sieved to optimal depth. Take GFN 22 for example: my card takes roughly 3 days to finish 1 candidate with OCL5. BUT, with the same 3 days of work, I was able to sieve a 275P range and remove 791 candiates rather than just 1. This should be enough of an explanation as to how poorly sieved it is.
May the sieve OCL app that also works on Intel and AMD GPUs save us from our misery (also, #sieving up to 400M B). | |
|
Michael GoetzVolunteer moderator
Project administrator
Send message
Joined: 21 Jan 10
Posts: 13804
ID: 53948
Credit: 345,369,032
RAC: 4,797
|
[or because the density of prime candidates after seiving is highest
Unfortunately, GFN ranges aren't sieved to optimal depth. Take GFN 22 for example: my card takes roughly 3 days to finish 1 candidate with OCL5. BUT, with the same 3 days of work, I was able to sieve a 275P range and remove 791 candiates rather than just 1. This should be enough of an explanation as to how poorly sieved it is.
May the sieve OCL app that also works on Intel and AMD GPUs save us from our misery (also, #sieving up to 400M B).
That's a VERY simplistic analysis, and misleading enough to easily be considered a falsehood.
GFN sieving works in a way such that the b range over which it's sieving doesn't affect how fast the sieve runs, but does affect how many factors it spits out.
Assume that we do 20K worth of B values with Genefer each year. The sieve is producing factors up to b=100,000,000. That's 5,000 years worth of Genefer runs. We can just as easily change the sieve to output factors up to b=400,000,000. If we do that (as we did with GFN15), that would increase the speed of which factors are output by a factor of 4. Does that change the optimal sieving point? Of course not.
This sieve is different in this regard from many other sieves. The number of candidates being tested usually affects the speed of the sieve. That's not true for GFN. The speed at which factors are produced is therefore rather arbitrary, and isn't a good gauge of where the optimal sieving depth is.
If you look at a more reasonable 20K range (one year's worth), you would expect to find, in your example, about 0.16 factors. By that metric, we're actually substantially over-sieved on GFN22.
If we assume we're sieving for a 10-year period, then we're getting about 1.6 factors from the sieve in the same time it takes to run one Genefer test, so if we look at a 10-year span we're slightly under sieved.
It would be idiotic to only sieve a small range, since we can sieve a b range of 100,000,000 just as quickly as we can sieve a range of 20,000. So of course we'll sieve it all at once. But that doesn't mean that we're going to define the optimal sieve point based upon 5 milennia's worth of Genefer testing!
(Also note that we currently double check Genefer but do not double check GFN sieving, so effectively the Genefer run-time, for this comparison, should be 6 days rather than three. That effectively doubles the optimal sieve point. I left that out for simplicity.)
EDIT: Look at it another way. With, for example, the ESP sieve, we sieved for something like 10 to 20 years worth of LLR tests. If we need more sieving later, we'll open it up again. But for now, it's optimally sieved. If we sieve GFN22 for 10 years worth of tests, we're almost optimally sieved now. But since we can sieve for an extra 4990 years worth of tests -- FOR FREE -- we're doing all that sieving right now so that there will never be a need to sieve again. But that doesn't change how deeply we want to sieve. We're getting all that extra sieving for free, so of course we're taking advantage of that ability.
____________
My lucky number is 75898524288+1 | |
|
RafaelVolunteer tester
Send message
Joined: 22 Oct 14
Posts: 906
ID: 370496
Credit: 479,176,653
RAC: 206,025
|
[or because the density of prime candidates after seiving is highest
Unfortunately, GFN ranges aren't sieved to optimal depth. Take GFN 22 for example: my card takes roughly 3 days to finish 1 candidate with OCL5. BUT, with the same 3 days of work, I was able to sieve a 275P range and remove 791 candiates rather than just 1. This should be enough of an explanation as to how poorly sieved it is.
May the sieve OCL app that also works on Intel and AMD GPUs save us from our misery (also, #sieving up to 400M B).
That's a VERY simplistic analysis, and misleading enough to easily be considered a falsehood.
GFN sieving works in a way such that the b range over which it's sieving doesn't affect how fast the sieve runs, but does affect how many factors it spits out.
Assume that we do 20K worth of B values with Genefer each year. The sieve is producing factors up to b=100,000,000. That's 5,000 years worth of Genefer runs. We can just as easily change the sieve to output factors up to b=400,000,000. If we do that (as we did with GFN15), that would increase the speed of which factors are output by a factor of 4. Does that change the optimal sieving point? Of course not.
This sieve is different in this regard from many other sieves. The number of candidates being tested usually affects the speed of the sieve. That's not true for GFN. The speed at which factors are produced is therefore rather arbitrary, and isn't a good gauge of where the optimal sieving depth is.
If you look at a more reasonable 20K range (one year's worth), you would expect to find, in your example, about 0.16 factors. By that metric, we're actually substantially over-sieved on GFN22.
If we assume we're sieving for a 10-year period, then we're getting about 1.6 factors from the sieve in the same time it takes to run one Genefer test, so if we look at a 10-year span we're slightly under sieved.
It would be idiotic to only sieve a small range, since we can sieve a b range of 100,000,000 just as quickly as we can sieve a range of 20,000. So of course we'll sieve it all at once. But that doesn't mean that we're going to define the optimal sieve point based upon 5 milennia's worth of Genefer testing!
(Also note that we currently double check Genefer but do not double check GFN sieving, so effectively the Genefer run-time, for this comparison, should be 6 days rather than three. That effectively doubles the optimal sieve point. I left that out for simplicity.)
Okay, let's look at the OCL3 range only, then. 6 factors VS 1 (actually, my last was 12, but the previous one was 6, so I'll stick to that). Doesn't seem well sieved to me. | |
|
Michael GoetzVolunteer moderator
Project administrator
Send message
Joined: 21 Jan 10
Posts: 13804
ID: 53948
Credit: 345,369,032
RAC: 4,797
|
Okay, let's look at the OCL3 range only, then. 6 factors VS 1 (actually, my last was 12, but the previous one was 6, so I'll stick to that). Doesn't seem well sieved to me.
OCL3 is about half the speed of OCL, so let's look just at the OCL range.
The OCL range of about b=540,000 is about 25 years worth of Genefer testing. About 1/200th of the sieve range. But I think a 10 year, 20,000 B range is more reasonable gauge. That's about 1.6 factors, or 3.2 including double checking (which we should). By that measurement we're still somewhat undersieved, so we should continue sieving. But not so much undersieved that it's ridiculous to be running Genefer. Because the speed at which factors are generated is completely arbitrary, there's no "Real" optimal sieving point. It's depends completely on how we choose to define the relevant sieving range. They say "1 week is a long time in politics." Well, 1 week is a really short time in prime hunting, but 25 years is certainly a long time. Even 10 years is a very long time.
____________
My lucky number is 75898524288+1 | |
|
RafaelVolunteer tester
Send message
Joined: 22 Oct 14
Posts: 906
ID: 370496
Credit: 479,176,653
RAC: 206,025
|
OCL3 is about half the speed of OCL, so let's look just at the OCL range.
The OCL range of about b=540,000 is about 25 years worth of Genefer testing. About 1/200th of the sieve range. But I think a 10 year, 20,000 B range is more reasonable gauge. That's about 1.6 factors, or 3.2 including double checking (which we should). By that measurement we're still somewhat undersieved, so we should continue sieving. But not so much undersieved that it's ridiculous to be running Genefer. Because the speed at which factors are generated is completely arbitrary, there's no "Real" optimal sieving point. It's depends completely on how we choose to define the relevant sieving range. They say "1 week is a long time in politics." Well, 1 week is a really short time in prime hunting, but 25 years is certainly a long time. Even 10 years is a very long time.
I went with OCL 3 as it goes faster on my card than OCl does, to make it fair with the 270P in 3 days rule (as I suppose this only applies to a Gtx 970). And the factors are conveniently counted in the stats page, so that was a plus for me.
Just a question: what was PrimeGrid doing 10y ago (on the GFN side of things)? I wasn't her to know. I kinda wonder how much it grew in computational power; likewise, I wonder how much we'll grow and how well that 25y estimate will hold. #Needs more crystal balls. | |
|
HonzaVolunteer moderator
Volunteer tester
Project scientist
Send message
Joined: 15 Aug 05
Posts: 1931
ID: 352
Credit: 5,703,800,670
RAC: 1,053,905
                            
|
Just a question: what was PrimeGrid doing 10y ago (on the GFN side of things)? I wasn't her to know. I kinda wonder how much it grew in computational power; likewise, I wonder how much we'll grow and how well that 25y estimate will hold. #Needs more crystal balls.
10 years ago?
It was second year of PrimeGrid and we had no GPU apps back then.
Mostly PrimeGen, TPS, PPS sieve and LLR was going on.
Yves Gallot did a lof of pioneering work on Genefer - even 15 years ago.
I've done weeks of CPU initial GFN Sieving on dozens of cores back in 2009 (where factors files were HUGE). It was a kick off for deeper sieving for GFN15-22 that still continues.
Prime testing was done using PRPNet, small community effort comparing to today's PG BOINC. Mostly manual effort, no double-checking.
Jim designed automatic sieving system about a year ago, and it helps the sieving effort a lot. And a lot of factor file files and other behind-the-scene effort.
GPU apps are there for about 5 years, IIRC. Sieving was obvious usage back then, historically CUDA.
Genefer went the BOINC way in early 2012. User friendly, double-checking etc.
With combined OCL app and - lately - support for new GPUs, very user friendly.
____________
My stats
Badge score: 1*1 + 5*1 + 8*3 + 9*11 + 10*1 + 11*1 + 12*3 = 186 | |
|
Michael GoetzVolunteer moderator
Project administrator
Send message
Joined: 21 Jan 10
Posts: 13804
ID: 53948
Credit: 345,369,032
RAC: 4,797
|
Just a question: what was PrimeGrid doing 10y ago (on the GFN side of things)? I wasn't her to know. I kinda wonder how much it grew in computational power; likewise, I wonder how much we'll grow and how well that 25y estimate will hold. #Needs more crystal balls.
That's an easy question: Nothing.
As far as I can tell the first GFN work started on PRPNet in October of 2009. That was CPU only, way before AVX, and most CPUs had only one or two cores. Quad core CPUs existed but weren't yet very common. Most new systems had 64 bit CPUs but still had 32 bit operating systems. Surprisingly, running 32 bit code had more of an effect on sieving than it did on LLR. In fact, we didn't even bother with a 64 bit LLR because it wasn't any faster. (The SIMD instructions aren't affected much when running on a 32 bit OS.)
____________
My lucky number is 75898524288+1 | |
|
RafaelVolunteer tester
Send message
Joined: 22 Oct 14
Posts: 906
ID: 370496
Credit: 479,176,653
RAC: 206,025
|
|
Okay, so I've had enough of the napkin math (and not knowing how the sieve goes on a per transform basis) and decided to put up a quick script on python to count the candidates usable by a given transform. Correct me if my math is wrong, but:
-I got my last few reservations, which spam a ~1050P range, glued them together and ran the script. There are 39 / 54 factors below the OCL / OCL4 Low range. Considering that only 1/3 of the candidates are actually removed from the sieve (the average is higher at around 40%, but I decided to play safe and go for 1/3 instead), we could approximate 13 / 18 candidates removed. GPU runs at 91.5P / day -> ~11.5 days of work.
-Leading edge for n=22 is b=73738. Running on OCL4 (fastest transform), it takes a bit over 68h, which is just shy of 2.84 days of work. Testing 4 candidates -> ~11.4 days of work, pretty close to the time spent sieving.
Going with the OCL alone (540,000), I can either remove 4 candidates with genefer or 13 with sieving + sieve other ranges as well.
So while I 100% agree with you that we shouldn't sieve until OCL4 High range, I'd say it should be sieved at least until the OCL one, in which case we're still ways away from optimal depth (well, on my particular GPU at least). | |
|
Scott BrownVolunteer moderator
Project administrator
Volunteer tester
Project scientist
Send message
Joined: 17 Oct 05
Posts: 2329
ID: 1178
Credit: 15,585,562,209
RAC: 14,154,657
                                         
|
Just a question: what was PrimeGrid doing 10y ago (on the GFN side of things)? I wasn't her to know. I kinda wonder how much it grew in computational power; likewise, I wonder how much we'll grow and how well that 25y estimate will hold. #Needs more crystal balls.
10 years ago?
It was second year of PrimeGrid and we had no GPU apps back then.
Mostly PrimeGen, TPS, PPS sieve and LLR was going on.
Actually, less than that (see here). 10 years ago, none of the current active PG projects existed. The only badge-eligible project running before 2007 was TPS (all twin prime checking is now folded into the SGS project). The oldest currently active projects (Cullen and Woodall prime searches) were begun in the summer of 2007.
____________
141941*2^4299438-1 is prime!
 | |
|
Message boards :
General discussion :
Prime Rank question |
