mersenneforum.org  

Go Back   mersenneforum.org > Great Internet Mersenne Prime Search > Software

Reply
 
Thread Tools
Old 2010-03-07, 22:00   #1
jasong
 
jasong's Avatar
 
"Jason Goatcher"
Mar 2005

5·701 Posts
Default Doing more about LL test verification

Won't stick around in here to bug you guys, but quick question:

Since Prime95 uses rounding to do its math, it seems inevitable to me that there be an error at some point which happens twice, and therefore generates the same residue. Basically, the cpu would be working properly, but the rounding error correction method might let a few bad calculations accidentally slide through. Is there ever going to be a dedicated program to go back, say, a decade from now and rerun this stuff with an integer-based LLR program? This is assuming of course that the floating point method stays tremendously faster.

Sorry if I phrased anything badly, hope it makes enough sense to be answered.
jasong is offline   Reply With Quote
Old 2010-03-07, 22:51   #2
axn
 
axn's Avatar
 
Jun 2003

11×421 Posts
Default

Quote:
Originally Posted by jasong View Post
Since Prime95 uses rounding to do its math, it seems inevitable to me that there be an error at some point which happens twice, and therefore generates the same residue. Basically, the cpu would be working properly, but the rounding error correction method might let a few bad calculations accidentally slide through. Is there ever going to be a dedicated program to go back, say, a decade from now and rerun this stuff with an integer-based LLR program? This is assuming of course that the floating point method stays tremendously faster.
Short answer: no.

Longer answer:
Quote:
Originally Posted by http://www.mersenne.org/various/math.php
GIMPS double-checking goes a bit further to guard against programming errors. Prior to starting the Lucas-Lehmer test, the S0 value is left-shifted by a random amount. Each squaring just doubles how much we have shifted the S value. Note that the mod 2P-1 step merely rotates the p-th bits and above to the least significant bits, so there is no loss of information. Why do we go to this trouble? If there were a bug in the FFT code, then the shifting of the S values ensures that the FFTs in the first primality test are dealing with completely different data than the FFTs in the second primality test. It would be near impossible for a programming bug to produce the same final 64 bit residues.
axn is offline   Reply With Quote
Old 2010-03-07, 22:53   #3
rogue
 
rogue's Avatar
 
"Mark"
Apr 2003
Between here and the

23·3·241 Posts
Default

Quote:
Originally Posted by jasong View Post
Won't stick around in here to bug you guys, but quick question:

Since Prime95 uses rounding to do its math, it seems inevitable to me that there be an error at some point which happens twice, and therefore generates the same residue. Basically, the cpu would be working properly, but the rounding error correction method might let a few bad calculations accidentally slide through. Is there ever going to be a dedicated program to go back, say, a decade from now and rerun this stuff with an integer-based LLR program? This is assuming of course that the floating point method stays tremendously faster.
There are checks in any good program using the FPU to verify that the rounding process hasn't introduced an error. Programs will compare the rounded result to the non-rounded result and throw and error if they differ by .5. The problem is that when you get a number like 123.5, one can't be certain if they really need to round up to 124 or down to 123. I know that most of the current programs by prime searching projects (pfgw, llr, phrot, genefer) actually look for differences lower than .4 rather than .5. A check of .4 is done because these programs don't check all instructions on all iterations of the FFT (as that would eliminate some of the advantage that the FPU provides). This does mean that it is possible that an error can occur that hasn't been detected, but this is why most projects require double-checks. The double-check is typically done on different hardware. If the residues match, then the result is most likely to be correct.

I'm certain that someone more familiar with the hardware level could explain more regarding the FPU and how it differs from machine to machine.
rogue is offline   Reply With Quote
Old 2010-03-08, 00:51   #4
jasonp
Tribal Bullet
 
jasonp's Avatar
 
Oct 2004

1101110001002 Posts
Default

The nature of the arithmetic used in the LL test is such that if one number out of millions is wrong in a given iteration, that error is propagated to the entire number in the next iteration. So if you even get one error in the course of an LL test, nothing beyond that point will be the same. So your hardware error would have to be in the same place at the same time to also fool a doublecheck run, which is sufficiently unlikely in a weeks-long test that nobody assumes it will happen.

The other danger in a long run like that is actual incorrect rounding, which would affect even perfectly working hardware. We use balanced representation, i.e. represent multiple-precision numbers as an array of positive or negative words. Multiplication results with this scheme are actually centered about zero on average, and the parameters chosen actually allow the possibility of a multiplication result not being able to fit in a 53-bit floating point mantissa. So if enough of the words in a multiple precision number had the same sign, the convolution would fail, even with no rounding error.

To combat this possibility, double check runs compute the Lucas-Lehmer test with the initial residue multiplied by a random power of two. This still allows the original residue to be recovered, but changes all the intermediate results used to compute it, and so a freakish roundoff error failure is not expected to repeat exactly. If instead the double check incurs its own freakish roundoff error, this is also okay; you can keep doing doublechecks until two runs with different initial shifts until you get a pair of them where freakish roundoff error does not occur.

So, bottom line, no archaeology on previous results is needed.
jasonp is offline   Reply With Quote
Old 2010-03-08, 01:22   #5
Prime95
P90 years forever!
 
Prime95's Avatar
 
Aug 2002
Yeehaw, FL

23×863 Posts
Default

Prime95 does more checking when running near the upper limit of an FFT size. If a roundoff error is between 0.4 and 0.6 the iteration is redone using a slower, but safer, method.

Thus, for an incorrect doublecheck to slip by, you'd need an LL test where the roundoff error was greater than 0.6 (very, very, rare) and the double-check LL test also had an error greater than 0.6 (very, very rare) and the resides matched (thanks to shifting of the initial FFT data this will happen 1 in 2^64 occurrences). Multiply that out and you get one *really* rare event, though not impossible.

Now let's say this really, really, really rare event happened. The chance that the corrected LL test yields a new Mersenne prime? Tack on another 1 in 300,000 chance.

In summary, I'm not losing any sleep that an undiscovered Mersenne prime lays among the doublechecked exponents.
Prime95 is online now   Reply With Quote
Old 2010-03-09, 17:10   #6
joblack
 
joblack's Avatar
 
Oct 2008
n00bville

52·29 Posts
Default

Quote:
Originally Posted by Prime95 View Post
Prime95 does more checking when running near the upper limit of an FFT size. If a roundoff error is between 0.4 and 0.6 the iteration is redone using a slower, but safer, method.

Thus, for an incorrect doublecheck to slip by, you'd need an LL test where the roundoff error was greater than 0.6 (very, very, rare) and the double-check LL test also had an error greater than 0.6 (very, very rare) and the resides matched (thanks to shifting of the initial FFT data this will happen 1 in 2^64 occurrences). Multiply that out and you get one *really* rare event, though not impossible.

Now let's say this really, really, really rare event happened. The chance that the corrected LL test yields a new Mersenne prime? Tack on another 1 in 300,000 chance.

In summary, I'm not losing any sleep that an undiscovered Mersenne prime lays among the doublechecked exponents.
I there no way around this problem?
joblack is offline   Reply With Quote
Old 2010-03-09, 17:32   #7
bsquared
 
bsquared's Avatar
 
"Ben"
Feb 2007

26×3×17 Posts
Default

Quote:
Originally Posted by joblack View Post
I there no way around this problem?

How paranoid are you? Lets say the chances of a very very rare event is 1 in 1000. So what we have here is the probability of 4 independent events happening with a combined probability of 1 in (1000 * 1000 * 2^64 * 300000).

There are approximately 3 * 10^23 primes between 0 and the number in parentheses, so one would need to do approximately that many LL tests and double checks before expecting one of them to mistakenly cover up the existence of a mersenne prime. If an LL test took 1 second on some hypothetical computer, you would need 10000 years with 1 trillion such computers to test this many exponents.

Last fiddled with by bsquared on 2010-03-09 at 17:32 Reason: typo
bsquared is offline   Reply With Quote
Old 2010-03-09, 19:15   #8
bsquared
 
bsquared's Avatar
 
"Ben"
Feb 2007

26·3·17 Posts
Default

Quote:
Originally Posted by bsquared View Post
There are approximately 3 * 10^23 primes between 0 and the number in parentheses, so one would need to do approximately that many LL tests and double checks before expecting one of them to mistakenly cover up the existence of a mersenne prime. If an LL test took 1 second on some hypothetical computer, you would need 10000 years with 1 trillion such computers to test this many exponents.
Actually, its longer than that, because the LL test is only run on prime exponents. So you'd need to run 5.5e30 LL tests and double checks, which would take 7 orders of magnitude longer with the same resources :)
bsquared is offline   Reply With Quote
Old 2010-03-09, 22:34   #9
joblack
 
joblack's Avatar
 
Oct 2008
n00bville

72510 Posts
Default

Quote:
Originally Posted by bsquared View Post
Actually, its longer than that, because the LL test is only run on prime exponents. So you'd need to run 5.5e30 LL tests and double checks, which would take 7 orders of magnitude longer with the same resources :)
I know that in operating system concepts even rare concurrency problems (SMP and deadlocks) are avoided. In software development the same concept should be implemented.
joblack is offline   Reply With Quote
Old 2010-03-09, 23:36   #10
jasonp
Tribal Bullet
 
jasonp's Avatar
 
Oct 2004

22×881 Posts
Default

One failed operation in 10^50 is not 'rare'; it can be safely described as 'impossible'.
jasonp is offline   Reply With Quote
Old 2010-03-09, 23:52   #11
cheesehead
 
cheesehead's Avatar
 
"Richard B. Woods"
Aug 2002
Wisconsin USA

22·3·641 Posts
Default

Quote:
Originally Posted by joblack View Post
I there no way around this problem?
(By "this problem", I assume you mean rounding errors.) Sure, there is: use only integer arithmetic.

Quote:
Originally Posted by joblack View Post
I know that in operating system concepts even rare concurrency problems (SMP and deadlocks) are avoided. In software development the same concept should be implemented.
Perhaps one should first do a cost-benefit analysis for the particular software in question.

As long as Intel (and others) keep cranking out CPUs with large amounts of circuitry dedicated to performing floating-point operations significantly faster than equivalent integer operations, integer-based GIMPS-related calculations will take significantly more time than floating-point implementations of the same calculations.

Since the FP rounding error probabilities can be reduced to extremely low values (according to some folks' scale, anyway) by using a relatively small amount of guarding calculation, it's generally deemed worthwhile for the sake of the large time savings. Furthermore, other error-detection and -avoidance measures (e.g., pseudorandom bit shifts with double-checking) have the effect of also reducing the likelihood that a FP rounding error will affect results.

A rare concurrency problem in an operating system could affect possibly-life-critical applications or otherwise have almost-unforeseeable consequences. An error in GIMPS simply does not pose risks of the same magnitude, and the consequences are confined to a small area of mathematics practically unconnected to other aspects of daily living.

You're welcome to develop further error-avoiding measures for addition to GIMPS FP routines -- or to use only integer-based FFT software -- if you deem it worthwhile to spend your time doing so.

Last fiddled with by cheesehead on 2010-03-10 at 00:00
cheesehead is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Modifying the Lucas Lehmer Primality Test into a fast test of nothing Trilo Miscellaneous Math 25 2018-03-11 23:20
Unsafe verification? CuriousKit PrimeNet 13 2015-06-21 14:49
Double check LL test faster than first run test lidocorc Software 3 2008-12-03 15:12
Will the torture test, test ALL available memory? swinster Software 2 2007-12-01 17:54
A primality test for Fermat numbers faster than P├ępin's test ? T.Rex Math 0 2004-10-26 21:37

All times are UTC. The time now is 19:57.

Fri Jul 3 19:57:11 UTC 2020 up 100 days, 17:30, 2 users, load averages: 1.30, 1.22, 1.33

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.