Double-checking with PFGW

[rogue]

I have been doing some testing with PFGW 3.3.6 and have discovered that a number of candidates need to be retested due to the carry propagation issue found in gwnum that was fixed in PFGW 3.3.6. It is possible that some primes have been missed. I'm opening this topic to discuss how we want to proceed.

For all of the bases I have reserved I have run the remaining k up to n = 1000 (my original script limit) to see if I missed any primes. Fortunately I did not. I then ran all tested candidates for n > 1000 against PFGW 3.3.5 and 3.3.6 using the -F switch. Around 8% of those candidates had a different FFT size. I updated the PRPNet database to force all of them to be retested. That should finish in the morning. At this time about 70% of those tests have completed. All residues match between 3.3.5 and 3.3.6, which means that none of those 70% were tripped up by the carry propagation issue.

Based upon testing I did with k*b^b+/-1 numbers, I did see numbers with invalid residues. IIRC it was about 3% of what remained after sieving, which is significant, especially since a number of primes were missed. The problem was more apparent as k increased. I didn't see any problems until k > 1000, but that was a small sample set. I am running an extended test overnight (2 < k < 2002, 3 < b < 1003, 402 < n < 10402) which will encompass over 1,000,000 tests. I should have some statistical results by the morning. In other words, I should be able to state, with a certain amount of confidence, the ranges of k, b, and n that should be retested.

I will state now that anyone using a pre-3.3.6 release should upgrade before continuing with any testing. According to George, base 2 should not be affected, but the higher the base, the more likely it is affected by the issue. Note that 3.3.6 will chose a larger FFT size for some numbers even if that is not required to complete a successful test. George is working on a permanent fix, but until I have one, 3.3.6 is the way to go for this project.

[gd_barnes]

This sounds very problematic. I'm open to any advice on how to proceed. I and I'm sure many others have done a large amount of work with PFGW 3.3.4, which I thought to be an excellent virtually bugfree version.

A couple of questions:

What is the "carry propagation" issue that you are referring to? If it's real technical, you don't need to provide a lengthy explanation. Just a quick synopsis will do.

Why test only k*b^b+/-1 ? What is significant about the base and exponent being the same? Wouldn't the bug exist across n-values that are not equal to the base?

[rogue]

All of us believed that gwnum 25.14 was bug-free. George was as surprised as anyone else that this was discovered.

George describes the issue here far better than I could.

The issue was discovered by kar_bon and 3.14159 when testing numbers of that form. b = n has no significance. It is just a coincidence.

PFGW Version 3.3.5.20101007.Win_Stable [GWNUM 25.14]

Special modular reduction using all-complex FFT length 768 on 9276*626^627+1
9276*626^627+1 is composite: RES64: [3E2E5E4CAE04201F] (0.0701s+0.0001s)

PFGW Version 3.3.6.20101007.Win_Stable [GWNUM 25.14]

Special modular reduction using zero-padded FFT length 896 on 9276*626^627+1
9276*626^627+1 is composite: RES64: [DD2C7BD5BCC04FAE] (0.0864s+0.0001s)

[vmod]

Gary: more info is in this thread especially post #65. k*b^b+/-1 searching was how the errors were initially noticed, but the problem apparently is not restricted to n=b.

Rogue: This is not very clear on the software section thread. Are N+1/N-1 tests as done by LLR 3.8.0 or 3.8.1 affected by the same issue?

I know you're not responsible for LLR but since this is a gwnum bug (used by both programs) and your technical understanding is far superior than mine any guess on LLR? Or any test cases to actually compare?

I've run a quick PFGW 3.3.5 vs 3.3.6 -F switch on about 25% of my total CRUS work (~80,000 tests, n>25K, several k's >1000). No FFT size mismatches. Maybe the problem is more prominent on smaller n and FFT sizes.

[CRGreathouse]

Originally Posted by gd_barnes

Why test only k*b^b+/-1 ?

That's just where the bug happened to be discovered. The problem shows up more readily with large bases, so this was a natural place to find it.

I hope statistical information is collected in terms of number of forms that need to be retested at a given base, and number of those that are wrong.

[rogue]

Originally Posted by vmod

This is not very clear on the software section thread. Are N+1/N-1 tests as done by LLR 3.8.0 or 3.8.1 affected by the same issue?

I know you're not responsible for LLR but since this is a gwnum bug (used by both programs) and your technical understanding is far superior than mine any guess on LLR? Or any test cases to actually compare?

I've run a quick PFGW 3.3.5 vs 3.3.6 -F switch on about 25% of my total CRUS work (~80,000 tests, n>25K, several k's >1000). No FFT size mismatches. Maybe the problem is more prominent on smaller n and FFT sizes.

LLR 3.8.x is also affected. I don't know if Jean is aware of the issue as he will need to re-release LLR.

According to George, smaller FFTs are affected.

Here are some statistics on what I ran overnight:

- about 6.7% of the numbers tested used a different FFT size
- the smallest k affected was 22 for 22*283^602+1
- the smallest b affected was 43 for 662*43^9802+1. For higher k, n as low as 1202 was affected for base 43
- the smallest n affected was 402 for 42*263^402+1
- I did not re-run any PRP tests to determine if residue did not match
- my other overnight test showed no residue differences for the bases I currently have reserved

Note that I skipped every 10 k, every 10 b, and every 100 n so these are ballpark ranges.

[rogue]

Originally Posted by gd_barnes

This sounds very problematic. I'm open to any advice on how to proceed. I and I'm sure many others have done a large amount of work with PFGW 3.3.4, which I thought to be an excellent virtually bugfree version.

I'm in that boat with you. I have spent a disproportionate amount of time on CRUS.

I certainly don't want to restart this project from scratch. Unless anyone thinks that it is imperative that we capture the lowest n for each k, I would avoid retesting any k for which a prime has been found. In other words, only the k without a prime should be retested.

This is what I suggest:

1) For 1 < n < 1000, use an ABC2 file to retest each remaining k.
2) For 1000 < n < 25000, sieve the remaining k to a shallow depth (no more than 1e10), then run the output through PFGW 3.3.5 and 3.3.6 with the -F switch. Use diff plus and editor to pull out the candidates where 3.3.5 and 3.3.6 used different FFT sizes. Run those candidates through PFGW 3.3.6. This will be anywhere from 3% to 10% of the output from the sieve.
3) For n > 25000, residues should be posted in one of the threads. Grab the tested candidates, run through PFGW 3.3.5 and 3.3.6 to find out which use different FFT sizes. Use diff plus and editor to pull out the candidates where 3.3.5 and 3.3.6 used different FFT sizes. Run those candidates through PFGW 3.3.6. This should be a fairly low percentage (most likely under 3%).

I know that this seems to be a HUGE amount of work, but I don't think it should be too bad except for S63.

For this project, I would no longer accept any results from PFGW 3.3.4 and earlier. I suggest that you start a "double-check" sticky thread with a list of conjectures and k that need to be verified along with the steps I enumerated. I think that the thread should request that participants spend some time verifying completed work before grabbing new reservations. Participants can quickly reserve and verify those k, thus removing them from the list. It should be possible to verify each k up to n = 25000 in less than an hour.

I know that it looks like there are about 275,000 k remaining, but note that about 237,000 are S63, which is grossly inaccurate. About 70,000 have only been tested to n = 1000. About 45,000 have been tested to n = 10,000 and the rest have been eliminated due to a found prime. I suspect that many of the lower bases (below base 35) probably require no retesting, but that does need to be verified. Outside of S63, that means that there are under 1,000 k that will need to be retested to any extent.

The question is, how do we get users up to PFGW 3.3.6 right now for any work they are currently doing so that when the submit their results, that we can trust the accuracy of them?

[KEP]

Rogue, does this have anything to do with the constant switch between "All-complex fft lengths" and "zero padded fft lengths"? Also does it always constitute a problem, if the k*b^n+c test has been tested using an All-complex fft length, wich is usually 40 % faster? There has been especially many all complex fft length tests under the s58 conjecture.

Now I must admit, that I'm very very close to cancelling all my reservations and discard all work as "bogus". There is also no way that I can double check any of my S58, S60 and S70 results, since it will mean that I will first complete these 2 reservations + 1 re-reservation, some time in 2015. So do you have any stats on how many primes I can expect to have missed, below my current test depth of n=65K for S58?

I'll exam further explanations and come to a final conclusion, on weather or not to cancel my CRUS work, as new information sees the light of the day...

I'm not mad, to say it for once, but I for one, am not going to spend several CPU years on producing mallock work and doublechecking previous work. I will however see if I can find version 3.3.6 somewhere and upgrade immediately.

Regards

KEP

[henryzz]

Originally Posted by KEP

Rogue, does this have anything to do with the constant switch between "All-complex fft lengths" and "zero padded fft lengths"? Also does it always constitute a problem, if the k*b^n+c test has been tested using an All-complex fft length, wich is usually 40 % faster? There has been especially many all complex fft length tests under the s58 conjecture.

Now I must admit, that I'm very very close to cancelling all my reservations and discard all work as "bogus". There is also no way that I can double check any of my S58, S60 and S70 results, since it will mean that I will first complete these 2 reservations + 1 re-reservation, some time in 2015. So do you have any stats on how many primes I can expect to have missed, below my current test depth of n=65K for S58?

I'll exam further explanations and come to a final conclusion, on weather or not to cancel my CRUS work, as new information sees the light of the day...

I'm not mad, to say it for once, but I for one, am not going to spend several CPU years on producing mallock work and doublechecking previous work. I will however see if I can find version 3.3.6 somewhere and upgrade immediately.

Regards

KEP

Just a very small amount needs to be doublechecked not the whole thing. Rogue said ~3%.

[henryzz]

I would suggest we should put this doublecheck work into a prpnet server to finish it quickly together. I am willing to test some candidates if someone posts a file.
Is 3.2.x affected?

[CRGreathouse]

Originally Posted by henryzz

Is 3.2.x affected?

I think yes.