PrimeGrid
Please visit donation page to help the project cover running costs for this month

Toggle Menu

Join PrimeGrid

Returning Participants

Community

Leader Boards

Results

Other

drummers-lowrise
1) Message boards : Generalized Fermat Prime Search : DO YOU FEEL LUCKY? (Message 162831)
Posted 7 days ago by GDB
Another benefit of sieving GFN-22 is that factors can be removed from GFN-23 without sieving,

GFN-23 [X] is a factor if GFN-22 [X*X] is a factor.
2) Message boards : Generalized Fermat Prime Search : DO YOU FEEL LUCKY? (Message 162807)
Posted 7 days ago by GDB
3 years ago when manual sieving was paused, I was
removing 400,000 GFN-22 factors for the range [2-400M] per year.
So, for 5 years, I could remove 2M factors.
My current hardware is 5 times faster, so that means I could remove 10M factors in 5 years.
Looking at a 1M range out of [2-400M] means I could sieve out 25,000 factors in 5 years.
Using GFN-22, I could only do 2,000 candidates in 5 years.


Without getting into the detailed math on this, your logic here is fundamentally flawed because it assumes a constant rate of sieving (i.e., that we have a constant rate of removal of factors). This simply is not true with sieves. The deeper we go into a sieve, the slower the removal of factors becomes...a great deal slower! In fact, the overwhelming majority of factors removed occurs earlier in the sieve. Indeed, it is quite likely that over a 5-year period as you note above, the number of factors removed during year one would exceed the number of factors removed over all 4 of the remaining years.

Additionally, there is also another assumption that may or may not be true, and that is that hardware improvements over those 5 years is consistent across applications. This is probably not the case. It could be that the sieve application actually gains more form the hardware improvements than the GFN application...it could be the opposite where the GFN app gains more (each, respectively, being an argument for more or less need of sieving). My own experiences over a largish variety of hardware and long-term experience is that the latter is more typical than the former, at least modestly.


Certainly sieving will slow down over time.
But, my contention is that sieving right now
will be more or a benefit for removing thousands of factors,
than using GFN to process 1 candidate at a time.

3) Message boards : Generalized Fermat Prime Search : DO YOU FEEL LUCKY? (Message 162805)
Posted 7 days ago by GDB
One thing you're missing. The 200,00 candidates being tested over 5 years actually
represent 200,000 plus 800,000 factors removed by sieving, equals a range of 1M covered in 5 years.
So, 1.4% x 1M = 14,000 candidates eliminated.
And that's with 1% GPUs used for sieving vs. GFN.
So, sieving removes factors at least 7 times faster than GFN.

The "improvement" is log(2.2·1021) / log(1.1·1021) = 20.17% / 19.89% = 1.014. It doesn't depend on ΔB, it is not 20.17% - 19.89% = 0.28%.
The number of remaining candidates at 1.1·1021 is 1.014 times the number of remaining candidates at 2.2·1021 (+1.4%).

We have 200,000 remaining candidates => ΔB = 1M. But 1M x 0.28% ~ 2,800 candidates.

At pmax ~ 1021, only one fifth of the factors remove a remaining candidate.


3 years ago when manual sieving was paused, I was
removing 400,000 GFN-22 factors for the range [2-400M] per year.
So, for 5 years, I could remove 2M factors.
My current hardware is 5 times faster, so that means I could remove 10M factors in 5 years.
Looking at a 1M range out of [2-400M] means I could sieve out 25,000 factors in 5 years.
Using GFN-22, I could only do 2,000 candidates in 5 years.
4) Message boards : Generalized Fermat Prime Search : DO YOU FEEL LUCKY? (Message 162802)
Posted 8 days ago by GDB
When I was manual sieving GFN-22, I was removing about 1,125 candidates a day by myself for the 100M range. Or, 22,500 candidates for a 2G range.
If I was running GFN, I could only test 1 or 2 a day.

The efficiency of sieving is decreasing with the sieve limit.
After sieving, the number of remaining candidates is about e · Cn · ΔB / log(pmax), where e = 0.56146, C22 = 17.41 and pmax is the sieve limit.
Today, for GFN-22, pmax = 1.1·1021. Then #cand ~ 0.2018 ΔB. The actual number of candidates in [2; 400M] is 80,693,547 => 20.17%.
If the sieve limit is doubled (2.2·1021), the ratio will be 19.89%. The improvement for GFN-22/DYFL projects is 1.4%.

Because of technological developments, sieving a range that will be tested 5+ years from now is a mistake.
In the coming five years, GFN-22/DYFL projects will test about 200,000 candidates.
N GPU-days are needed to sieve [1.1·1021; 2.2·1021]. It is estimated that if these N GPU-days are allocated to GFN-22/DYFL projects then more than 1.4% x 200,000 ~ 2,800 candidates are eliminated.


One thing you're missing. The 200,00 candidates being tested over 5 years actually
represent 200,000 plus 800,000 factors removed by sieving, equals a range of 1M covered in 5 years.
So, 1.4% x 1M = 14,000 candidates eliminated.
And that's with 1% GPUs used for sieving vs. GFN.
So, sieving removes factors at least 7 times faster than GFN.
5) Message boards : Generalized Fermat Prime Search : DO YOU FEEL LUCKY? (Message 162797)
Posted 8 days ago by GDB
From my understanding, GFN-22 was being sieved to 2G. Only the first 100M was being used.
The remainder of 2G results were being saved. So, it shouldn't be necessary to RESIEVE GFN-22 to get results up to 2G.
However, GFN-22 was severely undersieved for 2G. So a lot of NEW GFN-22 sieving needs to be done.

The full range [2; 2G] is sieved. The sieve limit depends on the computation time of a primility test not on the range size.
Today, GFN-22 + DYFL eliminate about 35,000 candidates each year, the equivalent of Δb ~ 200,000. 2G / 200,000 ~ 10,000 years.
GFN-22 is not undersieved, it would be if the range could be tested in few years.
2G is a huge range. More than 400 DYFL are expected in this range!


When I was manual sieving GFN-22, I was removing about 1,125 candidates a day by myself for the 100M range. Or, 22,500 candidates for a 2G range.

For GFN-23, I was removing 9.519 factors a day for 100M range. Or, 190,400 factors for a 2G range.

If I was running GFN, I could only test 1 or 2 a day.
6) Message boards : Generalized Fermat Prime Search : DO YOU FEEL LUCKY? (Message 162792)
Posted 8 days ago by GDB
GFN-22 is sieved to b=100M, so we can continue doing this search up to about 33.5 million digits. If we have to search larger numbers, we'll either need to sieve GFN-22 above 100M, or sieve GFN-23.
Since GIMPS has almost tested all n < 108M at least once, the next Mersenneprime could very well be larger than 33.5M digits (if n > 111.5M).

I can't say I'm not looking forward to manual sieving to finally get a ruby PSA badge.


From my understanding, GFN-22 was being sieved to 2G. Only the first 100M was being used.
The remainder of 2G results were being saved. So, it shouldn't be necessary to RESIEVE GFN-22 to get results up to 2G.
However, GFN-22 was severely undersieved for 2G. So a lot of NEW GFN-22 sieving needs to be done.
7) Message boards : Number crunching : Badges - Full Sets! (Message 162785)
Posted 9 days ago by GDB
20 subprojects turquoise or better,
8) Message boards : Number crunching : Badges IV (Message 162779)
Posted 9 days ago by GDB
My 8th sapphire badge.
9) Message boards : Number crunching : Badges IV (Message 162615)
Posted 15 days ago by GDB
My 11th Jade badge.
10) Message boards : Number crunching : Badges - Full Sets! (Message 162516)
Posted 19 days ago by GDB
With all active subprojects turquoise or better.


Next 10 posts
[Return to PrimeGrid main page]
DNS Powered by DNSEXIT.COM
Copyright © 2005 - 2023 Rytis Slatkevičius (contact) and PrimeGrid community. Server load 1.26, 1.85, 1.76
Generated 1 Jun 2023 | 16:53:10 UTC