Join PrimeGrid
Returning Participants
Community
Leader Boards
Results
Other
drummers-lowrise
|
Message boards :
Generalized Fermat Prime Search :
N=20, B=8
| Author |
Message |
|---|
|
|
|
http://www.primegrid.com/stats_genefer.php
The minimum b value in progress has been stuck at b=8 for quite awhile.
How can this task be taking so long? Not only has it already been cleared as b=64 at the n=19 level, but it just shouldn't take very long to test, even for a CPU!
Is something wrong?
In fact 8^1048576+1 = (2^3)^1048576+1 = (2^1048576)^3+1 which has an algebraic factor. So what's the deal? | |
|
 Michael Goetz Volunteer moderator
Project administrator
Send message
Joined: 21 Jan 10
Posts: 14037
ID: 53948
Credit: 477,051,011
RAC: 285,770
                               
|
|
There's at least an 11 day deadline on these tasks. Some people run large queues and/or run other projects, both of which can cause a delay in the start of processing. Additionally, many of these are being run on CPUs which require several days of crunching.
Finally, by default, BOINC doesn't even bother returning a task when it's completed and waits until the next time it requests work.
In other words, it's not late so there can't be any expectation that it should be complete.
By the way, if memory serves, that WU actually does have two completed results but they don't match so we're waiting for a third result. I'm not at home so it's not easy for me to check.
____________
My lucky number is 75898524288+1 | |
|
|
|
|
Frankly, I'm still a little disappointed that 2^3 is a b value being tested. I saw someone else post other examples of b^x that were being tested. It's just basic algebra... | |
|
Michael GoetzVolunteer moderator
Project administrator
Send message
Joined: 21 Jan 10
Posts: 14037
ID: 53948
Credit: 477,051,011
RAC: 285,770
|
|
After some deeper digging, the second result, from a CPU that crunched this task for 135 hours, was actually uploaded to the server two days before you asked the question.
As I mentioned above, however, the BOINC client's default behavior defers contacting the server to actually report the result as completed until either it needs to because the deadline is approaching, or it's contacting the server anyway to request more work.
In this case, the result was completed and uploaded to the server on December 5th. It has still not reported the result as completed. The deadline for doing so is late on December 10th.
____________
My lucky number is 75898524288+1 | |
|
|
|
http://www.primegrid.com/stats_genefer.php
The minimum b value in progress has been stuck at b=8 for quite awhile.
How can this task be taking so long? Not only has it already been cleared as b=64 at the n=19 level, but it just shouldn't take very long to test, even for a CPU!
Is something wrong?
In fact 8^1048576+1 = (2^3)^1048576+1 = (2^1048576)^3+1 which has an algebraic factor. So what's the deal?
I also want to ask why we do not skip those b values which are perfect powers.
For example with 8 = 2^3 as above, where 3 is not a power of two, since:
x^3 + 1 = (x + 1) (x^2 - x + 1)
we know right away that (2^1048576)^3 + 1 is divisible by 2^1048576 + 1.
The same thing happens whenever b is a perfect power whose exponent contains an odd prime factor.
And when b is in itself a perfect square of the form b = a^{2^k}, with k>0, then this prime candidate really belongs to another GFN exponent "level". For example the test of b=16:
16^1048576+1 = GF(20, 16) = GF(21, 4) = GF(22, 2) = F(22)
belongs to the n=22 level. In the same way b=1296 should be skipped since
1296^1048576+1 = GF(20, 1296) = GF(21, 36) = GF(22, 6)
I recently noticed this phenomenon in a post in another thread.
So the request is: Could we please skip the b values (4, 8, 16, 32, 36, 64, 100, 128, 144, 196, 216, 256, 324, 400, 484, 512, 576, 676, 784, 900, 1000, 1024, 1156, 1296, 1444, 1600, etc.) which are perfect powers?
/JeppeSN | |
|
JimBHonorary cruncher
Send message
Joined: 4 Aug 11
Posts: 920
ID: 107307
Credit: 989,505,342
RAC: 19,336
             
|
|
We do eliminate some candidates in the way you're talking about. Hundreds of them. Right now I'm a little too sleep-deprived to figure all this out and I'm trying to fix things that have a far more significant effect on our site than running a few extra tests.
I believe a lot of this stuff wasn't put into effect on 524288 because those tests were so fast. Now that we're getting beyond the b-limit of what GPUs can handle, we may want to revisit it at some point in the future. We do not, however, consider it a large problem, and most likely not an effective way to spend the limited resources available to us. A few extra tests is a small drop in a very large bucket.
| |
|
axnVolunteer developer
Send message
Joined: 29 Dec 07
Posts: 285
ID: 16874
Credit: 28,027,106
RAC: 0
            
|
In the same way b=1296 should be skipped since
1296^1048576+1 = GF(20, 1296) = GF(21, 36) = GF(22, 6)
So, you want to avoid testing the same number using a smaller FFT and use a larger FFT instead?! Testing GF(22, 6) takes 4 times as much time as testing GF(20, 1296). | |
|
|
|
We do eliminate some candidates in the way you're talking about. Hundreds of them. Right now I'm a little too sleep-deprived to figure all this out and I'm trying to fix things that have a far more significant effect on our site than running a few extra tests.
I believe a lot of this stuff wasn't put into effect on 524288 because those tests were so fast. Now that we're getting beyond the b-limit of what GPUs can handle, we may want to revisit it at some point in the future. We do not, however, consider it a large problem, and most likely not an effective way to spend the limited resources available to us. A few extra tests is a small drop in a very large bucket.
OK, it could be interesting to hear what b values we do eliminate.
Of course checking if b is a perfect power, b=a^k, or not is extremely fast, much easier than e.g. sieving for small factors of GF(n, b).
/JeppeSN | |
|
|
|
In the same way b=1296 should be skipped since
1296^1048576+1 = GF(20, 1296) = GF(21, 36) = GF(22, 6)
So, you want to avoid testing the same number using a smaller FFT and use a larger FFT instead?! Testing GF(22, 6) takes 4 times as much time as testing GF(20, 1296).
My first thought is if GF(22, 6) is already tested, no matter how fast testing GF(20, 1296) would be, it would be useless to do it since both are just different ways of writing the same number.
And you do realize that any number GF(22, a) can be seen as belonging to any of the smaller n series, since:
GF(22, a) = GF(21, a^2) = GF(20, a^4) = GF(19, a^8) = ... = GF(1, a^2097152) = GF(0, a^4194304)
In particular if GF(20, ·) is always faster to check than GF(22, ·), then for every number we can use the identity GF(22, a) = GF(20, a^4) to gain this advantage. However, the much larger base value a^4 must somehow spoil this plan, at least for "usually" large a values, otherwise checking generalized Fermat numbers would be "too easy".
In practice, the number GF(n, a^2) has almost always been checked earlier, historically, in the form with much smaller base, that is GF(n+1, a). So we should exclude bases b=a^2.
/JeppeSN | |
|
axnVolunteer developer
Send message
Joined: 29 Dec 07
Posts: 285
ID: 16874
Credit: 28,027,106
RAC: 0
|
|
Found this thread: http://www.primegrid.com/forum_thread.php?id=4644 | |
|
|
|
Found this thread: http://www.primegrid.com/forum_thread.php?id=4644
Interesting. So we have removed some perfect-power b in the past.
I don't know if anyone has a clear picture of what b values were skipped, and what were not. Can one see a list of all work units belonging to n=20 and n=22 somewhere? For the PRPNet subprojects (n=15,16,18,19) I can see a list of work units in progress (but I cannot see the work units finished or those yet unassigned).
If for n=22 we did not skip perfect-square b, we have shown that GF(24, 10) = GF(22, 10000) and GF(24, 12) = GF(22, 20736) are composite. If that is the case, someone should inform Wilfrid Keller or whoever updates prothsearch.com, for the b=10 Summary and the b=12 Summary claim that the cases GF(24, 10) and GF(24, 12) are Character unknown. Should be: Composite but no factor known. Unless we found factors during our sieving, of course!
/JeppeSN | |
|
Michael GoetzVolunteer moderator
Project administrator
Send message
Joined: 21 Jan 10
Posts: 14037
ID: 53948
Credit: 477,051,011
RAC: 285,770
|
I don't know if anyone has a clear picture of what b values were skipped, and what were not. Can one see a list of all work units belonging to n=20 and n=22 somewhere? For the PRPNet subprojects (n=15,16,18,19) I can see a list of work units in progress (but I cannot see the work units finished or those yet unassigned).
As a general rule, we have not made the results of primality tests generally available -- meaning, you can't just go to the website and download them. There's a few not-so-obvious reasons for that.
The results are not secret nor proprietary, so we are happy to make them available to anyone who wants the information. However, to my knowledge, nobody has ever expressed an interest in this data before, and without some sort of request or use case, we're only guessing about what information would be useful.
So if you want this kind of data, just ask, and let us know what you want it for so we can put something together that suits your needs. Understand, however, that not all of the results are online, so I might not be able to give you what you need. Also, some data that people might want might not be available at all.
____________
My lucky number is 75898524288+1 | |
|
|
|
|
Michael Goetz, this is just out of curiosity.
I wanted to check if we skip impossible b values such as b=a^3, b=a^5, b=a^6, etc. Both in the PRPNet GFN subprojects and in the BOINC GFN subprojects.
I wanted to also check if we skip b values of the form b=a^{2^j} (with a not itself a perfect power) which may be prime, but which will in many cases be redundant because they were checked earlier in a "larger" subproject. In the forum post i linked above I saw that we did assign the PRPNet task 910116^524288+1 to someone even if 910116^524288+1 = 954^1048576+1 which means that we already knew the result. GF(19, 910116) = GF(20, 954).
I also wanted to see if GF(22, 10000) = 10000^{2^22}+1 and GF(22, 20736) = 20736^{2^22}+1 have been checked or skipped, as I said above, these are GF(24, 10) and GF(24, 12), respectively.
When, for a given subproject, the b values get big, the perfect powers appear relatively rarely, so it is not a massive optimization to skip them, but it would still be interesting to see if we skip or not.
For each b, let f(b) be the maximal exponent i possible when writing b on the form b=a^i, then f is tabulated here (OEIS A052409). The case f(b)=1 is the normal one. When f(b)>1, we either have f(b) is a power of two (primality possible, but might be checked already in another subproject) or f(b) contains an odd prime factor (GFN(n, b) then has an algebraic divisor and is composite).
/JeppeSN | |
|
Michael GoetzVolunteer moderator
Project administrator
Send message
Joined: 21 Jan 10
Posts: 14037
ID: 53948
Credit: 477,051,011
RAC: 285,770
|
I wanted to check if we skip impossible b values ...
Short answer: we try to.
However, we don't try with the same compulsiveness that someone searching on their own would do. Small scale searching and large scale distributed computing have significant differences.
If I'm searching on my own, my biggest constraint is almost always going to be the amount of hardware I own, can buy, or can rent. My own time is virtually unlimited. As such, it's paramount to squeeze every last drop of computing out of what I've got and not waste any of it.
On a big distributed project, it's very different. I've got essentially unlimited computing power at my fingertips. If we need to push some calculation for whatever reason, all we have to do is ask and plenty of people will come and help. Being a little less efficient -- either by doing more double checking, or, as in this case, running a few unnecessary tests -- has a very small effect on the overall computation.
On the other hand, the time we might need to spend to eliminate every last redundant test is time we could spend doing something else, which might enable lots more computing to be done, as opposed to computing more efficiently. When I'm doing my own searching, increasing efficiency is the only way to do more searching, so it's natural for people, like yourself, with a background in prime searching, to focus on efficiency. But from my perspective, we usually get more bang for the buck by trying to get more total computing done than to increase efficiency.
It's not that efficiency isn't important, because it is. It's just not nearly as important as is the total computing effort.
That's why we spend far more time on trying to reduce the number of errors people have and widening the range of hardware that can be used. That's going to benefit us more than spending time thinking about eliminating a handful of tests.
That being said, those tests kind of fall into the "low hanging fruit" category, so we do have a program that eliminates the ones that have been mentioned. But it's not likely to be worth the time to repeatedly rehash this discussion trying to find a few more tests that can be skipped. As such this will probably be my last comment on this topic, since we seem to repeating the same statements over and over.
____________
My lucky number is 75898524288+1 | |
|
Message boards :
Generalized Fermat Prime Search :
N=20, B=8 |
