Author 
Message 
Michael GoetzVolunteer moderator Project administrator
Send message
Joined: 21 Jan 10 Posts: 14037 ID: 53948 Credit: 477,051,011 RAC: 285,770

The short GFN tasks (n=19 or N=524288) are currently at around b=660K. Work is loaded up to b=700K.
We expect the CPUbased GenefX64 program to start to fail around b=735K, so at b=700K we will shift to n=20 (N=1048576) for the short tasks. This will likely occur within the next 4 to 8 weeks.
Once that shift occurs, you can expect the short tasks to initially run about twice as long as they do today. Within a few months, as b increases, run times will gradually increase until they are about 4 times as long as they are today.
Once we start crunching n=20 on BOINC, we will restart n=19 on PRPNet, where you can continue to crunch on either the CPU or GPU. Expect the CPU crunching to shift to Genefer80 at around b=735K. That will increase the processing time of each WU by a factor of about 3x. GPU crunching can continue until about b=815K, at which point the crunching will also need to shift to Genefer80.
____________
My lucky number is 75898^{524288}+1 


Michael GoetzVolunteer moderator Project administrator
Send message
Joined: 21 Jan 10 Posts: 14037 ID: 53948 Credit: 477,051,011 RAC: 285,770

UPDATE 19Nov: The leading edge is now at 680K. The switch to n=20 will likely occur within the next week; two weeks at most.
____________
My lucky number is 75898^{524288}+1 



UPDATE 19Nov: The leading edge is now at 680K. The switch to n=20 will likely occur within the next week; two weeks at most.
The sieving effort for n=20 is still going on, right?
____________
676754^262144+1 is prime 



UPDATE 19Nov: The leading edge is now at 680K. The switch to n=20 will likely occur within the next week; two weeks at most.
The sieving effort for n=20 is still going on, right?
Yep, there's still about 8000P left to be sieved to reach the target. If a couple more people help out with sieving using their GPU it should be feasible I think :)
____________
PrimeGrid Challenge Overall standings  Last update: From Pi to Paddy (2016)



Michael GoetzVolunteer moderator Project administrator
Send message
Joined: 21 Jan 10 Posts: 14037 ID: 53948 Credit: 477,051,011 RAC: 285,770

UPDATE 19Nov: The leading edge is now at 680K. The switch to n=20 will likely occur within the next week; two weeks at most.
The sieving effort for n=20 is still going on, right?
Yes. It's also still ongoing for n=21 and n=22, and will be for many, many years.
____________
My lucky number is 75898^{524288}+1 



UPDATE 19Nov: The leading edge is now at 680K. The switch to n=20 will likely occur within the next week; two weeks at most.
The sieving effort for n=20 is still going on, right?
Yep, there's still about 8000P left to be sieved to reach the target. If a couple more people help out with sieving using their GPU it should be feasible I think :)
Just moved a gpu there. I hope that that move will not make me miss a prime on the last 20k left t crunch on Boinc :)
By the way, how do the nvidia 6xx series behave there? are they faster or slower than previous series?
____________
676754^262144+1 is prime 


Michael GoetzVolunteer moderator Project administrator
Send message
Joined: 21 Jan 10 Posts: 14037 ID: 53948 Credit: 477,051,011 RAC: 285,770

Yep, there's still about 8000P left to be sieved to reach the target.
And when that target is met, we'll set another target. :)
We only really ever stop sieving when we reach the point where it's no longer efficient to sieve as compared with doing a primality test (LLE, Genefer, etc.) on every remaining candidate.
With GFN, since the run time for Genefer increases approximately 4fold every time n goes up by one, and since the rate at which factors are found roughly decreases by 50% as P doubles, the optimal sieve point (i.e., the point where we stop sieving) for successively higher n's increases dramatically.
For n=19 (the old short tasks), that point was close to 18446P (a natural break point for the sieving program), so we stopped there. Let's call that 18E for simplicity.
For n=20 (the new short tasks), the natural stopping point is about 100E. It's currently sieved to almost 22E.
For n=21, the natural stopping point is about 500E. It's currently sieved to 20E.
For n=22 (our World Record search), the natural stopping point is about 1000E. It is currently sieved to about 35E.
____________
My lucky number is 75898^{524288}+1 


Michael GoetzVolunteer moderator Project administrator
Send message
Joined: 21 Jan 10 Posts: 14037 ID: 53948 Credit: 477,051,011 RAC: 285,770

Just moved a gpu there. I hope that that move will not make me miss a prime on the last 20k left t crunch on Boinc :)
You can continue to crunch n=19 on PRPNet once it ends on BOINC. The limit we're hitting is for GenefX64, not GeneferCUDA, so you can continue to use a GPU on PRPNet for about another 100K worth of b values.
If your goal is to find a really big prime number, that's what I would recommend. There's no better place to find a mega prime.
By the way, how do the nvidia 6xx series behave there? are they faster or slower than previous series?
I don't own one, so I can't say from experience, but I would expect it to be substantially faster than the 5xx series. It's only double precision apps, like Genefer, that suffer on the Kepler GPUs.
____________
My lucky number is 75898^{524288}+1 


axnVolunteer developer Send message
Joined: 29 Dec 07 Posts: 285 ID: 16874 Credit: 28,027,106 RAC: 0

I don't own one, so I can't say from experience, but I would expect it to be substantially faster than the 5xx series. It's only double precision apps, like Genefer, that suffer on the Kepler GPUs.
The few numbers I've seen in PST forum** indicates that a 680 is substantially slower (about 20%??) than a 580 in GFN sieve! I have a hunch why this is so. From the numbers I've seen, each SMX in the 680 (192 CUDA cores) can support 192 adds, but only 32 muls (integer ops) per cycle. The sieve code, unfortunately, relies heavily on the muls, so...
People should play around with the various B settings, running multiple copies, etc. to get the most thruput out of their GPU.
** We really should get some systematic benchmarks. 



n=19 leading edge has reached (and stopped growig) 700k a few day ago.
Has n=20 already been loaded (no info on that on se subproject status page)? If not, when will it be?
Thanks in advance
____________
676754^262144+1 is prime 


Michael GoetzVolunteer moderator Project administrator
Send message
Joined: 21 Jan 10 Posts: 14037 ID: 53948 Credit: 477,051,011 RAC: 285,770

n=19 leading edge has reached (and stopped growig) 700k a few day ago.
Has n=20 already been loaded (no info on that on se subproject status page)? If not, when will it be?
Thanks in advance
That number doesn't indicate what one would imagine it does.
On that page, "leading edge" is defined as the most recent work unit that was created. It's not the most recent work unit that was sent out to a client.
Usually, there isn't a big difference between the two, but one of the side effects of the server problem we had a few days ago was that the work generator went bonkers and generated ALL of the remaining n=19 WUs.
Because of the way leading edge is calculated for that page, this caused the leading edge to instantly jump right to the end, at 700k.
The actual leading edge, as of a few minutes ago, is 692900. At the rate we're going, I expect the n=19 WUs to run dry before the week is out.
Note that under normal circumstances, the server keeps a buffer of up to 1000 short GFN WUs generated and ready to be sent out. Therefore, the leading edge that's shown on that page is always a bit higher than what was actually sent out. For n=19, 1000 WUs is about a 3 day supply.
____________
My lucky number is 75898^{524288}+1 


Michael GoetzVolunteer moderator Project administrator
Send message
Joined: 21 Jan 10 Posts: 14037 ID: 53948 Credit: 477,051,011 RAC: 285,770

UPDATE: N=19 leading edge is now 694896. 841 WUs to go.
____________
My lucky number is 75898^{524288}+1 


Michael GoetzVolunteer moderator Project administrator
Send message
Joined: 21 Jan 10 Posts: 14037 ID: 53948 Credit: 477,051,011 RAC: 285,770

UPDATE: n=19 leading edge is now 698318. 282 WUs to go.
The last WU should be sent out in the next 24 hours. After that, it's just waiting for the results to come back in and issuing resends for tasks that return errors.
____________
My lucky number is 75898^{524288}+1 


Michael GoetzVolunteer moderator Project administrator
Send message
Joined: 21 Jan 10 Posts: 14037 ID: 53948 Credit: 477,051,011 RAC: 285,770

N=20 tasks are now being sent out. N=19 tasks, mostly resends, will also continue to be sent out until all of the 524288 work units are completed and verified.
N=20 tasks currently have a deadline of 15 days, although some of the earliest may have a deadline of 11 days. The very smallest of these tasks are actually shorter than the old n=19 tasks, but most will be larger. The longest n=20 sent out so far is about 60% longer than the n=19 tasks (about 9 hours on my GTX 460 vs 5.5 hours for the old tasks.) This will rapidly increase to about 2.5 to 3 times as long as the old tasks over the next couple of days.
____________
My lucky number is 75898^{524288}+1 


axnVolunteer developer Send message
Joined: 29 Dec 07 Posts: 285 ID: 16874 Credit: 28,027,106 RAC: 0

The very smallest of these tasks are actually shorter than the old n=19 tasks, but most will be larger.
Any b < sqrt(700000) = 836 would be redundant since it would have been tested as part of n = 19. :(
[eg: 6^1048576 = 36^524288] 


Michael GoetzVolunteer moderator Project administrator
Send message
Joined: 21 Jan 10 Posts: 14037 ID: 53948 Credit: 477,051,011 RAC: 285,770

The very smallest of these tasks are actually shorter than the old n=19 tasks, but most will be larger.
Any b < sqrt(700000) = 836 would be redundant since it would have been tested as part of n = 19. :(
[eg: 6^1048576 = 36^524288]
Indeed, that is true. If we had thought of this, we could've considered removing them.
I think we would have crunched the numbers with b below sqrt(100000) regardless, but we could of skipped candidates with sqrt(100000) < b < sqrt(700000).
____________
My lucky number is 75898^{524288}+1 


HonzaVolunteer moderator Volunteer tester Project scientist Send message
Joined: 15 Aug 05 Posts: 1963 ID: 352 Credit: 6,402,773,857 RAC: 2,541,172

Any b < sqrt(700000) = 836 would be redundant since it would have been tested as part of n = 19. :(
[eg: 6^1048576 = 36^524288]
And we could intentionally test some high b's above CUDA limits for n=19 using n=20, right?
____________
My stats 



Has the "default block size" (what one gets by specifying 0 on the PG preferences page) been changed for optimal performance for n=20 (vs 19)? It looks like from stderr.txt it has changed from 7 to 8. Just wanted to confirm I'm not misconfigured somehow.
Gary 


axnVolunteer developer Send message
Joined: 29 Dec 07 Posts: 285 ID: 16874 Credit: 28,027,106 RAC: 0

Any b < sqrt(700000) = 836 would be redundant since it would have been tested as part of n = 19. :(
[eg: 6^1048576 = 36^524288]
And we could intentionally test some high b's above CUDA limits for n=19 using n=20, right?
The reverse doesn't work (always). Only if b is a perfect square, can we do the reverse. You could say that, for example, by testing 13768^1048576+1, you've automatically tested 189557824^524288+1. But that is neither here nor there :)
PS: 189557824 = 13768^2 


Michael GoetzVolunteer moderator Project administrator
Send message
Joined: 21 Jan 10 Posts: 14037 ID: 53948 Credit: 477,051,011 RAC: 285,770

Has the "default block size" (what one gets by specifying 0 on the PG preferences page) been changed for optimal performance for n=20 (vs 19)? It looks like from stderr.txt it has changed from 7 to 8. Just wanted to confirm I'm not misconfigured somehow.
Gary
It varies somewhat from platform to platform. On Windows and Mac, both 19 and 20 use shift=7. On Linux, 19 uses 7 and 20 uses 8.
____________
My lucky number is 75898^{524288}+1 



Have enough n=20 units been run to give out average run times by card?
____________
@AggieThePew




Have enough n=20 units been run to give out average run times by card?
Average times are quite useless on low b. My first n20 (b=544) took over 40k seconds. Last n19 took 22k seconds. 550ti@1026MHz.
____________
676754^262144+1 is prime 


Michael GoetzVolunteer moderator Project administrator
Send message
Joined: 21 Jan 10 Posts: 14037 ID: 53948 Credit: 477,051,011 RAC: 285,770

Have enough n=20 units been run to give out average run times by card?
Run times are predictable, so we don't need to run a bunch to get fairly accurate estimates.
Times for a GTX 460: (with percentage relative to recent n=19 tasks)
b=50: 6:31:35 (117%)
b=100: 7:40:57 (137%)
b=500: 10:22:03 (185%)
b=1,000: 11:31:26 (206%)
b=5,000: 14:12:32 (254%)
b=10,000: 15:21:55 (274%)
b=50,000: 18:03:01 (322%)
b=100,000: 19:12:23 (343%)
b=500,000: 21:53:29 (390%)
For reference, the old n=19 tasks, specifically 700000^524288+1 took 5:35:57.
GTX 580 times will be about 50% of the times listed above.
GTX 680 times will be about 60% of the times listed above.
If you know how long your computer took to do the old tasks, you can use the chart above to estimate how long it will take to do the new tasks. If it took 5 hours (300 minutes before), and you're doing a task with b close to 1000, it will take about 10 hours and 18 minutes. (300 * 2.06 = 618)
____________
My lucky number is 75898^{524288}+1 


Michael GoetzVolunteer moderator Project administrator
Send message
Joined: 21 Jan 10 Posts: 14037 ID: 53948 Credit: 477,051,011 RAC: 285,770

Assuming that we do find at least one prime with N=1048576, where would such a prime rank in the overall list?
As of today, the 4 known primes at N=524288 rank in positions 16, 13, 12, and 11 on the all time largest prime list.
Primes with N=1048576 would rank as follows:
(There may appear to be gaps in the number sequences below, for example, b=10. That's because the missing numbers were removed by sieving.)
 b <= 8 have less than 1 million digits, and are the only two candidates that would not be megaprimes if they were indeed prime.
 12 <= b <= 272 would be lower than 16th place on the list, i.e., smaller than all of the N=524288 primes.
 276 <= b <= 418 would be the 16th largest prime number.
 430 <= b <= 584 would be the 14th largest prime number. (15 and 14 are so close together so there are no remaining candidates that are larger than 15 but smaller than 14.)
 586 <= b <= 596 would be the 13th largest prime number.
 618 <= b <= 684 would be the 12th largest prime number.
 692 <= b <= 5462 would be the 11th largest prime number.
(Note that, as axn mentioned above, all b <= 836 are already known to be composite due to work done on N=524288. Therefore, the lowest possible prime we will find with N=1048576 will rank 11th on the list.)
 5464 <= b <= 7332 would be the 10th largest known prime.
 7350 <= b would rank 9th on the list.
____________
My lucky number is 75898^{524288}+1




I think GFN n=20 (cpu version) is now (or will be very soon) the longest subproject on Primegrid (longer than SoB).
____________
676754^262144+1 is prime 


Michael GoetzVolunteer moderator Project administrator
Send message
Joined: 21 Jan 10 Posts: 14037 ID: 53948 Credit: 477,051,011 RAC: 285,770

I think GFN n=20 (cpu version) is now (or will be very soon) the longest subproject on Primegrid (longer than SoB).
Hmmmm....
Ok, on my machine (no AVX), this is what the leading edge of SoB looks like using llr64:
C:\PRPNet\prpclient5.0.8windowsgpu\prpclient2gpu>llr64 d q"67607*2^20905411+1"
Starting Proth prime test of 67607*2^20905411+1
Using allcomplex FFT length 1920K, Pass1=384, Pass2=5K, a = 3
67607*2^20905411+1, bit: 10000 / 20905427 [0.04%]. Time per bit: 38.210 ms.
That works out to 221.88 hours.
This is what GenefX64 looks like at the b limit (several years from now):
C:\PRPNet\prpclient5.0.8windowsgpu\prpclient2gpu>genefx64 q "600000^1048576+1"
...
Estimated total run time for 600000^1048576+1 is 267:32:17
Of course, by the time we get to b=600K, the leading edge of SoB will have advanced quite a bit too, so those WUs will also be somewhat longer.
____________
My lucky number is 75898^{524288}+1 



I bet the limit will be reached before the end of 2013 (unless NASA is wrong about the end of the world in a fortnight... ).
My last SoB took 75 hours (with AVX). Genefer does not benefit from AV . Leading edge would take ~70 hours on my rig.
____________
676754^262144+1 is prime 


Michael GoetzVolunteer moderator Project administrator
Send message
Joined: 21 Jan 10 Posts: 14037 ID: 53948 Credit: 477,051,011 RAC: 285,770

I bet the limit will be reached before the end of 2013 (unless NASA is wrong about the end of the world in a fortnight... ).
My last SoB took 75 hours (with AVX). Genefer does not benefit from AV . Leading edge would take ~70 hours on my rig.
Not counting increases in computer power, I'm thinking the end of 2015.
Going from b=110K to b=700K took about 9 months. The n=20 tasks are about 4 times as long and we're searching from b=0K to b=600K (roughly the same number of candidates as with n=19), so if nothing else is different, I expect this to take 3 years.
____________
My lucky number is 75898^{524288}+1 


axnVolunteer developer Send message
Joined: 29 Dec 07 Posts: 285 ID: 16874 Credit: 28,027,106 RAC: 0

After looking thru the candidates in http://home.comcast.net/~jimb_primegrid/guess20.txt, I've identified the following 15 candidates that can be removed from consideration:
65536 (F24)
131072 (2^17)
524288 (2^19),
7776 (6^5)
20736 (WR b=12)
38416 (WR b=14)
104976 (WR b=18)
234256 (WR b=22)
331776 (WR b=24)
456976 (WR b=26)
21952 (28^3)
614656 (WR b=28)
175616 (56^3)
343000 (70^3)
373248 (72^3)
These are either already tested (F24 and various WR candidates) or are have an algebraic factor and hence cannot be prime. I fear it might be too late for 7776, but the others can be removed. 


JimBHonorary cruncher Send message
Joined: 4 Aug 11 Posts: 920 ID: 107307 Credit: 989,505,342 RAC: 19,336

axn, would you mind explaining in onesyllable words why the following candidates should be removed?
7776 (6^5)
21952 (28^3)
175616 (56^3)
343000 (70^3)
373248 (72^3)



axnVolunteer developer Send message
Joined: 29 Dec 07 Posts: 285 ID: 16874 Credit: 28,027,106 RAC: 0

I'll use zerosyllable words :)
(a^b)^c = a^(bc) = (a^c)^b
7776^1048576+1 = (6^5)^1048576+1 = (6^1048576)^5+1
x^n+1 is divisible by x+1 if n is an odd integer. (This is the reason behind all GFNs having perfect power of 2's as their exponent)
Therefore, (6^1048576)^5+1 is divisible by 6^1048576+1.
Likewise, for others.
EDIT: This is actually the reason for nominating 2^17 and 2^19 as well. 


JimBHonorary cruncher Send message
Joined: 4 Aug 11 Posts: 920 ID: 107307 Credit: 989,505,342 RAC: 19,336

Thinking about all this, I've finally written a few programs to find candidates that could be eliminated for various reasons. I will be removing these candidates from the corresponding sieves in the next day or so.
Candidates like the ones axn explained above can be found here. I'm only listing items not already eliminated by sieving, otherwise this list would be a lot longer.
Candidates that can be eliminated because of primetesting at n=22 can be found here. Only about half the n=21 candidates could be removed right now, but by the time we start primetesting there, n=22 will be far past b=10K. The "in sieve" or "removed" part refers to the n=22 sieve. If the number had been removed from the lower n sieve, it doesn't appear at all.
If there are any other methods of eliminating candidates, I"m interested in hearing about them. 


axnVolunteer developer Send message
Joined: 29 Dec 07 Posts: 285 ID: 16874 Credit: 28,027,106 RAC: 0

These can be removed because they're (known composite) Fermat numbers:
256^524288+1 = 16^1048576+1 = 4^2097152+1 = 2^4194304+1 (F22: known factor 3853959202444067657533632211*2^24+1)
65536^1048576+1 = 256^2097152+1 = 16^4194304+1 [ = 4^8388608+1 = 2^16777216+1 ] (F24: proven composite with Pepin's test)
Their status can be found here: http://www.prothsearch.com/fermat.html
Also, when n=21 starts testing, we can remove from consideration, all b < sqrt(600000) [ b limit for n=20] using the 2021 equivalence. 

