Getting reliable LL from unreliable hardware

[Prime95]

Originally Posted by GP2

But I'm looking at preda's recent PRP primality tests, for example for M78424979, and they are all Type 1. And gpuOwL has implemented Gerbicz checks since v 1.0 last August.

Or does Type 1 mean something different for PRP primality vs. PRP cofactor testing?

You are correct. I'll amend my statement to:

Type 1 does not do Gerbicz error-checking for Mersenne cofactor testing.

[kriesel]

Originally Posted by Madpoo

Right now we have all this data on bad results, but we don't know at what point along the way they went off the rails. I think it'd be an interesting thing to see at what point a bad result became bad. Could be surprising if we saw that most go astray early on...might alter some double-check strategies one way or another.

Plus, it'd be kind of interesting if someone is doing a double-check and comparing their residues at fixed intervals... if they mismatch, some kind of message could pop up to let them know. Nothing scary, because there's every reason to think the previous run was bad, not theirs. I'd hate to have people abandon and start over because they thought they had a problem...

So yeah... like a res64 early on that we could somewhat easily check to make sure they didn't just BS the whole thing, and then at something like 10%-25% intervals?

The server has more room now to store that kind of data...could be cool.

I had a cllucas double check of roughly 62.8m go bad around 17.15m. Hundreds of hours of what looked like correct function, then suddenly the interim residues are all 0x02. That's when I discovered periodic savefiles had been consistently failing. The rerun from scratch should finish today and looks ok so far.

While interim residues every 10M or 20M iterations may be often enough, it might be useful to have the first 10k displayed on screen, with a check for the known-bad-interim residues applied, and the run terminated if it's a known-bad residue for the application or algorithm. (0x02 is bad, as long as it's the LL test, independently of whether it's CUDALucas, clLucas, or other LLtester.) It would also generate a lot of quick-to-run known-good residues along the way. Some of the applications lack residue duplication selftests for all the supported fft lengths. An early check would be a chance to catch the ones that were started with seriously inadequate fft lengths, as sometimes happens with new users not understanding the bits/word constraints, or simple typos in manually entered fft lengths.

Back in the days of prime95 V18, 19, & 20 QA, we had volunteers comparing interim 64-bit residues in parallel runs by email. My recollection was there was not a pattern found of when things fail. That may have been due to a small data set of mismatches, or may be due to the absence of a pattern.

In the case of a detected discrepancy between a user's run and one other user's interim residue(s), a clear message indicating it may be an issue with their run, or may be an issue with the other's run, and please continue the run, would be good. Something like

"A difference has been detected between your run's interim residue 0x0123456789abcdef at iteration 10M for M87654321 and another run's interim residue 0xfedcba09876543__ at iteration 10M for M87654321. This may indicate an issue with your run, or an issue with the other run. Please continue your run."

If it's a case of triple checking or higher and the user's run is outvoted by others, then what?

[kriesel]

I think what George meant here is
x^2 is recalculated by (x+r)(x-r) + r^2 (plus not minus),
since (x+r)(x-r) = x^2 +rx -rx -r^2 = x^2-r^2.
Then (x+r)(x-r)+r^2 = x^2 but probably dodging numerical inaccuracies previously encountered by directly computing x^2.
I think it unlikely a flipped sign would get into George's code, or survive long there if it did.

Originally Posted by Prime95

There are other ways past difficult iterations. If prime95 sees a roundoff error > 28/64 then it goes back to the last save file and redoes the iteration by computing (x+random)(x-random) - random^2.

BTW, prime95 does do roundoff checking every iteration when operating near the limit of an FFT size. It does roundoff checking every 128 iterations when not operating near the limit of an FFT size.

I agree with preda, that these tricks will not push the maximum exponent too much higher. "NeverOddOrEven" used these tricks (in the extreme) to do LL testing at 604M whereas prime95's default for that FFT size is 596M.

[GP2]

Originally Posted by kriesel

I had a cllucas double check of roughly 62.8m go bad around 17.15m.

I had an Mlucas double-check of M48939799 on Google Compute Engine go bad between 18.76M and 18.77M, as determined by a subsequent mprime run with InterimResidues turned on. My only bad result ever.

As regards the cause: With both mprime and Mlucas, when an FFT size is found to be too small, the run continues with a larger FFT size. However mprime takes the additional step of rewriting the worktodo line with an additional FFT2= field, so that the new FFT size continues to be used if a run is interrupted and resumed. However the current version of Mlucas doesn't do that, and when using preemptible instances on GCE, the run is interrupted at least once every 24 hours. So every time it resumed it tried the original FFT size again, and one of the times was unlucky.

I think mprime is also much more conservative than Mlucas when it comes to setting a roundoff error threshold that triggers a higher FFT size. I think mprime uses a threshold around 0.24 whereas with Mlucas an error of 0.4375 did not trigger a higher FFT size. From what George wrote above, mprime also only goes back to the last savefile if the error is above 28/64 = 0.4375. But it also sometimes runs a test to see if the average roundoff error is above around 0.24, in which case it goes to a higher FFT size.

[ewmayer]

Originally Posted by GP2

I had an Mlucas double-check of M48939799 on Google Compute Engine go bad between 18.76M and 18.77M, as determined by a subsequent mprime run with InterimResidues turned on. My only bad result ever.

As regards the cause: With both mprime and Mlucas, when an FFT size is found to be too small, the run continues with a larger FFT size. However mprime takes the additional step of rewriting the worktodo line with an additional FFT2= field, so that the new FFT size continues to be used if a run is interrupted and resumed. However the current version of Mlucas doesn't do that, and when using preemptible instances on GCE, the run is interrupted at least once every 24 hours. So every time it resumed it tried the original FFT size again, and one of the times was unlucky.

Thanks to your bug report, the fix for this is already tested in my under-development v18 code; it involves tacking on 3 bytes to the existing savefile format, which encode the FFT length which was being used at time of the savefile write (specifically 3 bytes to hold (n >> 10), where n is unpadded FFT length, always a multiple of 1 Kdouble.) On restart-form-interrupt, this datum is used to set FFT length, overriding the usual start-of-run default. I've implemented the fix in such a way that pre-v18 savefile (lacking the extra trailing bytes) can be used as input to a v18 binary invocation; if the program hits EOF when it tries to read the extra bytes it just uses the default FFT length based on exponent and starts tacking on the extra bytes at the next savefile write.

[JeppeSN]

Originally Posted by axn

If by false postitive you mean a correctly executed PRP test declares a composite number to be "probable prime" (aka discovery of a pseudoprime), then the answer is infinitesimal**. Seriously, a pseudoprime is much much rarer than an actual prime. Prime probability is on the order of 1/log(N). IIRC, pseudoprime probability is on the order of 1/N

** hyperbole

Of course, if this new paradigm leads to the discovery of a composite Mersenne number which is a genuine 3-PRP, remember to announce this find! Because it would in a sense be more interesting than a new Mersenne prime.

(I think R. Gerbicz conjectured early in this thread that pseudoprimes of this kind do not exist.)

/JeppeSN

[LaurV]

My belief is that there is no 3-PSP mersenne numbers. Of course I have no freaking idea how to prove that... but something similar to fermat numbers should take place...

[GP2]

Most of the time when a first-time type-5 PRP-CF test is done, it shows up as "Unverified (Reliable)". For example, M8072983 and many others.

In a few cases, though, it appears simply as "Unverified", without the "(Reliable)". What determines this?

I don't think it's the error code, because M7823429 had error-code "00100000" in my results.txt file, but it still displays as "Unverified (Reliable)"

Edit: Hmm, but on the other hand M6753847 had error-code "01000100" in my results.txt file, and that one does display as "Unverified" without the "(Reliable)".



Most of the non-Reliable cases of Unverified were subsequently double-checked and verified, but in the case of M4622869 there is a mismatch. This is the first type-5 mismatch that I'm aware of, the first case where a Gerbicz-checked type-5 residue is incorrect.

My own type-5 result is "Unverified (Reliable)" while the other type-5 result is just "Unverified".

Note that this exponent was already double-checked with type-1 residues, but another user poached the exponent and submitted a type-5 residue. I manually double-checked that today and got a mismatch. I've already asked ATH to do the triple-check for 4622869 and the double-check for 6753847.



This suggests that Unverified without Reliable might be given a higher priority for early double-checking, especially if we ever get any for type-5 residues with non-cofactor PRP testing of first-time exponents in the 70M ranges.

[ATH]

It matched your type 5 residue, to the original type 5 residue is bad.

[Prime95]

Originally Posted by GP2

Most of the non-Reliable cases of Unverified were subsequently double-checked and verified, but in the case of M4622869 there is a mismatch. This is the first type-5 mismatch that I'm aware of, the first case where a Gerbicz-checked type-5 residue is incorrect.

Looking at the full JSON result text, the bad run was done without Gerbicz error-checking. Perhaps the user was getting a lot of rollbacks, looked in undoc.txt, and turned off Gerbicz error checking.

Without looking at Aaron's PHP code I bet the (reliable) text is only output if Gerbicz error-checking was used.

[GP2]

Originally Posted by Prime95

Looking at the full JSON result text, the bad run was done without Gerbicz error-checking. Perhaps the user was getting a lot of rollbacks, looked in undoc.txt, and turned off Gerbicz error checking.

Without looking at Aaron's PHP code I bet the (reliable) text is only output if Gerbicz error-checking was used.

Hmm, that makes sense. My type-5 result for M6753847 also had no mention of Gerbicz error-checking in the JSON in results.txt. It dated from last October, and has now been verified.

I guess I assumed type-5 was synonymous with Gerbicz, but I guess they weren't introduced simultaneously. The JSON says the result for M6753847 used 29.4 build 1.