mersenneforum.org  

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

Reply
 
Thread Tools
Old 2010-01-27, 05:42   #1
petrw1
1976 Toyota Corona years forever!
 
petrw1's Avatar
 
"Wayne"
Nov 2006
Saskatchewan, Canada

3×37×47 Posts
Default Double check of factoring??

I understand that LL/DC errors (i.e. incorrect results) are generally caused by hardware errors.

Is it not possible, likewise, for similar hardware errors to cause invalid factor results; i.e. reporting a factor when there really isn't one and thereby eliminating the exponent from LL/DC, erronously?
petrw1 is offline   Reply With Quote
Old 2010-01-27, 05:51   #2
sdbardwick
 
sdbardwick's Avatar
 
Aug 2002
North San Diego County

10111001112 Posts
Default

IIRC, the server checks the validity of the factor when reported.
sdbardwick is offline   Reply With Quote
Old 2010-01-27, 06:00   #3
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

3·1,993 Posts
Default

Quote:
Originally Posted by petrw1 View Post
Is it not possible, likewise, for similar hardware errors to cause invalid factor results; i.e. reporting a factor when there really isn't one and thereby eliminating the exponent from LL/DC, erronously?
It's easy to check that the submitted factors are correct. The only kind of error you'd need to worry about is that no factor is reported when there is, in fact, a small factor. But even then the only cost is that the number will need to be LL'd.
CRGreathouse is offline   Reply With Quote
Old 2010-01-27, 07:39   #4
cheesehead
 
cheesehead's Avatar
 
"Richard B. Woods"
Aug 2002
Wisconsin USA

769210 Posts
Default

Quote:
Originally Posted by petrw1 View Post
Is it not possible, likewise, for similar hardware errors to cause invalid factor results;
Yes ...

Quote:
i.e. reporting a factor when there really isn't one and thereby eliminating the exponent from LL/DC, erronously?
... but, unlike the situation with LL tests, factor verification doesn't require a rerun of the entire process (TF, P-1, ECM, ...) by which the factor was found. A split-second arithmetic calculation is all that's required, and (as sdbardwick pointed out) the server does that whenever it receives a factor-found report.

Last fiddled with by cheesehead on 2010-01-27 at 07:44
cheesehead is offline   Reply With Quote
Old 2010-01-27, 18:34   #5
chalsall
If I May
 
chalsall's Avatar
 
"Chris Halsall"
Sep 2002
Barbados

22×5×232 Posts
Default

Quote:
Originally Posted by cheesehead View Post
Yes ...

... but, unlike the situation with LL tests, factor verification doesn't require a rerun of the entire process (TF, P-1, ECM, ...) by which the factor was found. A split-second arithmetic calculation is all that's required, and (as sdbardwick pointed out) the server does that whenever it receives a factor-found report.
Yes... But...

This will detect false positives, but not false negatives...
chalsall is online now   Reply With Quote
Old 2010-01-27, 19:00   #6
cheesehead
 
cheesehead's Avatar
 
"Richard B. Woods"
Aug 2002
Wisconsin USA

22·3·641 Posts
Default

Quote:
Originally Posted by chalsall View Post
This will detect false positives,
... which is exactly what the OP meant by "i.e. reporting a factor when there really isn't one and thereby eliminating the exponent from LL/DC, erronously", which I quoted in my reply. :-)

Last fiddled with by cheesehead on 2010-01-27 at 19:45 Reason: New Year's resolution: Remember the [strike]Alamo[/strike][strike]Maine[/strike] emoticons!
cheesehead is offline   Reply With Quote
Old 2010-01-27, 19:06   #7
chalsall
If I May
 
chalsall's Avatar
 
"Chris Halsall"
Sep 2002
Barbados

245248 Posts
Default

Quote:
Originally Posted by cheesehead View Post
... which is exactly what the OP meant by "i.e. reporting a factor when there really isn't one and thereby eliminating the exponent from LL/DC, erronously", which I quoted in my reply.
Yes... Sorry.

But... a LL is *very* expensive.

Thus, while a false negative won't allow a prime to be missed, it would waste resources.

I have always wondered why Prime95 doesn't return a residual for factoring work which could only be produced by doing the full amount of work without error.

This would allow "spot checks" of factoring producers (at least, those using Prime95), which was the point I was trying to make.
chalsall is online now   Reply With Quote
Old 2010-01-27, 19:41   #8
Mini-Geek
Account Deleted
 
Mini-Geek's Avatar
 
"Tim Sorbera"
Aug 2006
San Antonio, TX USA

427810 Posts
Default

Quote:
Originally Posted by chalsall View Post
Yes... Sorry.

But... a LL is *very* expensive.

Thus, while a false negative won't allow a prime to be missed, it would waste resources.

I have always wondered why Prime95 doesn't return a residual for factoring work which could only be produced by doing the full amount of work without error.

This would allow "spot checks" of factoring producers (at least, those using Prime95), which was the point I was trying to make.
Unless I'm mistaken, the odds of a false negative TF would be so astronomically lower than the odds of an incorrect LL residue that it's really just not worth the effort to double check.
Let's say you've got hardware that has a 2% chance of a single error over 30 days of work (be it TF or LL). For simplicity's sake, we'll assume an error on a TF always produces a negative for the factor being checked.
Let's say you make one computation error during a TF to 2^64. There's a 1/64th chance (assuming http://www.mersenne.org/various/math.php is right) of there being a factor anywhere in there. According to http://mersenne-aries.sili.net/throughput.php?cpu=AMD+Athlon%28tm%29+64+X2+Dual+Core+Processor+4800%2B|512|0&mhz=2500, there are about 1,136,364 TF iterations in that range. I'm not sure if 1 iteration=1 factor, but let's assume so. So there's about a 1/(64*1,136,364) chance that the one computation error was during a factor, rendering a false negative. That's a 0.000001375% chance of a missed factor for every error your computer makes. And this CPU could do about 389 TFs to 2^64 per 30 days. That means that there's a 2% chance that one out of 389 TFs would have a tiny chance of a missed factor, or a 0.000000000275% chance of a missed factor. Unless I'm making some false assumptions, or have done something really stupid here, I'd say that's well worth the risk, despite the large cost difference between LL and TF.
Mini-Geek is offline   Reply With Quote
Old 2010-01-27, 20:31   #9
chalsall
If I May
 
chalsall's Avatar
 
"Chris Halsall"
Sep 2002
Barbados

22×5×232 Posts
Default

Quote:
Originally Posted by Mini-Geek View Post
Unless I'm mistaken, the odds of a false negative TF would be so astronomically lower than the odds of an incorrect LL residue that it's really just not worth the effort to double check.
But we've already seen many instances of ranges which were TFed (using other software, admittedly) which then needed to be retested.

These were only found by way of statistical analysis (and perhaps this is the most optimal way -- I don't know).

But I stand by my argument that it *might* be good if the Prime95 client returned a unique residual even for TF work.

After all, if LL and DC work fails to execute deterministically on the CPUs out there, surely TF (and P-1 and ECM) work does as well?

And I'm not arguing for a standard "Double-check" of TF work. Simply the ability to do so for participants and/or machines which *might* be questionable. After all, a single bad machine can result in *many* bad results. And a bad participant can result in many *many* bad results.

Those far more learned than myself might be able to speak to this question more deeply.

Last fiddled with by chalsall on 2010-01-27 at 20:41 Reason: Added "And I'm not aruging...
chalsall is online now   Reply With Quote
Old 2010-01-27, 20:55   #10
cheesehead
 
cheesehead's Avatar
 
"Richard B. Woods"
Aug 2002
Wisconsin USA

22×3×641 Posts
Default

Quote:
Originally Posted by Mini-Geek View Post
Unless I'm mistaken, the odds of a false negative TF would be so astronomically lower than the odds of an incorrect LL residue that it's really just not worth the effort to double check.

< snip >

For simplicity's sake, we'll assume an error on a TF always produces a negative for the factor being checked.

< snip >

So there's about a 1/(64*1,136,364) chance that the one computation error was during a factor, rendering a false negative. That's a 0.000001375% chance of a missed factor for every error your computer makes.

< snip >

Unless I'm making some false assumptions
There does seem to be an assumption there that a computation error would affect the checking of only one candidate factor.

What if there's a computation error affecting the increment between candidate factors or the screening-out of candidates divisible by small primes? Then one error could affect many candidates by causing large numbers of potential factors not to be tested. Up to a whole bit level -- zillions of candidates -- could be erroneously reported negative, when not a single candidate on that level was actually tested.

My guess is that there is much less chance that a single error systematically affects large numbers of candidates than that it affects only the test of a single candidate. But that smaller chance should be multiplied by the large number of candidates affected if it happens, to properly judge the impact.
cheesehead is offline   Reply With Quote
Old 2010-01-27, 21:09   #11
lfm
 
lfm's Avatar
 
Jul 2006
Calgary

1A916 Posts
Default

I'd think the (slim) chance of accidental false negatives wouldn't warrant massive double checking. The subsequent LL test(s) will settle the matter of primality after all. Only if you're keen to find factors of known composites would it be of interest.

Also the P-1 and ECM searches seem to perform an implicit check for missed factors.

If there is systematic false negatives either a bug or fraud, they should show up in statistics I think since the odds of finding factors are fairly well known aren't they? If there's any statistical outliers by account or by program/version then rechecking a sampling might be warranted.
lfm is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Double Check Unregistered Information & Answers 3 2011-10-01 04:38
First check and double check llrnet servers. opyrt Prime Sierpinski Project 3 2009-01-02 01:50
Double-check check? M0CZY Software 15 2008-10-30 14:20
Here's why we double-check... gd_barnes No Prime Left Behind 0 2008-02-11 19:23
Double Check P-1 PhilF PrimeNet 6 2005-07-03 14:36

All times are UTC. The time now is 02:11.


Fri Aug 12 02:11:35 UTC 2022 up 35 days, 20:58, 2 users, load averages: 1.16, 1.18, 1.23

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2022, 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.

≠ ± ∓ ÷ × · − √ ‰ ⊗ ⊕ ⊖ ⊘ ⊙ ≤ ≥ ≦ ≧ ≨ ≩ ≺ ≻ ≼ ≽ ⊏ ⊐ ⊑ ⊒ ² ³ °
∠ ∟ ° ≅ ~ ‖ ⟂ ⫛
≡ ≜ ≈ ∝ ∞ ≪ ≫ ⌊⌋ ⌈⌉ ∘ ∏ ∐ ∑ ∧ ∨ ∩ ∪ ⨀ ⊕ ⊗ 𝖕 𝖖 𝖗 ⊲ ⊳
∅ ∖ ∁ ↦ ↣ ∩ ∪ ⊆ ⊂ ⊄ ⊊ ⊇ ⊃ ⊅ ⊋ ⊖ ∈ ∉ ∋ ∌ ℕ ℤ ℚ ℝ ℂ ℵ ℶ ℷ ℸ 𝓟
¬ ∨ ∧ ⊕ → ← ⇒ ⇐ ⇔ ∀ ∃ ∄ ∴ ∵ ⊤ ⊥ ⊢ ⊨ ⫤ ⊣ … ⋯ ⋮ ⋰ ⋱
∫ ∬ ∭ ∮ ∯ ∰ ∇ ∆ δ ∂ ℱ ℒ ℓ
𝛢𝛼 𝛣𝛽 𝛤𝛾 𝛥𝛿 𝛦𝜀𝜖 𝛧𝜁 𝛨𝜂 𝛩𝜃𝜗 𝛪𝜄 𝛫𝜅 𝛬𝜆 𝛭𝜇 𝛮𝜈 𝛯𝜉 𝛰𝜊 𝛱𝜋 𝛲𝜌 𝛴𝜎𝜍 𝛵𝜏 𝛶𝜐 𝛷𝜙𝜑 𝛸𝜒 𝛹𝜓 𝛺𝜔