mersenneforum.org  

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

Reply
 
Thread Tools
Old 2018-01-27, 09:50   #1
6pac
 
Jan 2018

5 Posts
Default GIMPS double-checking certainty rate

Hi,

I've read this: https://www.mersenne.org/various/math.php

Overall, I'm wondering if GIMPS achieves 100% certainty on the primality test? Does the double-checking step ensures 100% certainty and if so, can you please elaborate a little bit on how it works? Why re-running Lucas-Lehmer ensure 100% certainty? What changes between runs?

As side questions, I was wondering :

1) Is the convolution error check so slow, that hypothetically, it could not be used at every step and finish in less than, say, 10 years?

2) Have you tested the all-integer weighted transform which as far as I can tell should be lossless? Hypothetically, could it not be used to perform a primarily test and finish in less than, say, 10 years?

Thank you,
6pac is offline   Reply With Quote
Old 2018-01-27, 10:52   #2
LaurV
Romulan Interpreter
 
LaurV's Avatar
 
"name field"
Jun 2011
Thailand

10,273 Posts
Default

Quote:
Originally Posted by 6pac View Post
What changes between runs?
It is called "shift". See here. (the link is to the last section, called "double checking", but the page is built in such a way that you can't go below the bottom of the page, that is why it seems that link starts in the middle of the "LL" section)
LaurV is offline   Reply With Quote
Old 2018-01-27, 14:44   #3
retina
Undefined
 
retina's Avatar
 
"The unspeakable one"
Jun 2006
My evil lair

2×32×7×53 Posts
Default

Quote:
Originally Posted by 6pac View Post
Overall, I'm wondering if GIMPS achieves 100% certainty on the primality test?
No it doesn't. It only validates the last 64-bits of the remainder for non-primes. So in theory there can be a 1 in 2^64 chance of an invalid test matching the final residue.

So for there to be a missed prime there would have to be two bad tests that manage to match on the final 64-bits. By my probably incorrect maths that would be approximately a (1 in 2^64) * (4%^2) chance, where 4% is the average error rate.

Primes are a wholly different manner and are checked much more thoroughly, many times on many systems. The chances of a false prime are considerably smaller than having a missed prime. Still not 100%, but approaching very very close to it.

Last fiddled with by retina on 2018-01-27 at 15:01 Reason: "a having" --> "having a"
retina is online now   Reply With Quote
Old 2018-01-27, 14:54   #4
Uncwilly
6809 > 6502
 
Uncwilly's Avatar
 
"""""""""""""""""""
Aug 2003
101×103 Posts

5·7·311 Posts
Default

Quote:
Originally Posted by retina View Post
Primes are a wholly different manner and are checked much more thoroughly, many times on many systems. The chances of a false prime are considerably smaller than a having missed prime. Still not 100%, but approaching very very close to it.
Interim residues for primes are also cross checked. Such that the chance of errors is even lower. If every 10,000,000 iterations we compare the residue, that drives down probability of errors causing the a false positive. Also, using different FFT sizes reduces the probability that other errors sneak in.
Uncwilly is offline   Reply With Quote
Old 2018-01-27, 15:11   #5
6pac
 
Jan 2018

5 Posts
Default

edited

Is 100% achievable in a practical amount of processing time (say 10 years)? Maybe we've done it before for some big Mi?

Last fiddled with by 6pac on 2018-01-27 at 15:50
6pac is offline   Reply With Quote
Old 2018-01-27, 16:15   #6
GP2
 
GP2's Avatar
 
Sep 2003

3×863 Posts
Default

Quote:
Originally Posted by 6pac View Post
What changes between runs?
As LaurV pointed out, the shift changes.

Also the hardware changes. Different people use different computers. The principal source of error is hardware problems. Sometimes people overclock their machines past the point of reliability, sometimes a bit gets flipped by cosmic rays, or maybe the hardware is just crap to begin with. It takes only one tiny error in one calculation among tens of millions to invalidate the whole result.

Also the chips change, and the version of the program changes. Maybe the first LL test was done eight years ago with a Nehalem microarchitecture that used SSE2 and the second LL test was done a few months ago with a Skylake using AVX512. Or maybe the second test used a different program altogether like Mlucas, or CUDALucas and gpuOwL, which use the graphics card instead of the CPU.

Quote:
Originally Posted by 6pac View Post
Is 100% achievable in a practical amount of processing time (say 10 years)?
The potential sources of erroneous results include hardware unreliability, algorithmic implementation flaws, and human malice. Current procedures provide a high degree of confidence, but I don't know what would constitute "100%" certainty that a Mersenne number is composite, short of discovering a factor.
GP2 is offline   Reply With Quote
Old 2018-01-27, 19:45   #7
6pac
 
Jan 2018

5 Posts
Default

Quote:
Originally Posted by GP2 View Post
I don't know what would constitute "100%"
You can get 100% certainty by computing Lucas-Lehmer using fix-point math. Distinct hardware gives different floating point results (FPU, SIMD, GPU). ALU though is deterministic across same family of hardware (I've first hand experience regarding this on x86-64). Now can you compute Lucas-Lehmer using fix-point math in a practical amount of time, I dont know.

Last fiddled with by 6pac on 2018-01-27 at 20:03
6pac is offline   Reply With Quote
Old 2018-01-27, 20:12   #8
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dartmouth NS

100000111000102 Posts
Default

Quote:
Originally Posted by 6pac View Post
You can get 100% certainty by computing Lucas-Lehmer using fix-point math. Distinct hardware gives different floating point results (FPU, SIMD, GPU). ALU though is deterministic across same family of hardware (I've first hand experience regarding this on x86-64). Now can you compute Lucas-Lehmer using fix-point math in a practical amount of time, I dont know.
Assuming no hardware errors, no programming errors, no bit flips in the process, etc.
science_man_88 is offline   Reply With Quote
Old 2018-01-27, 21:05   #9
6pac
 
Jan 2018

5 Posts
Default

Quote:
Originally Posted by science_man_88 View Post
Assuming no hardware errors, no programming errors, no bit flips in the process, etc.
I see what you mean. I guess there is two possible views on that. You could be a nazi (for lack of better term) and say "because of say, programming errors, 100% is not doable, you will always have to cross-check the result" (which is correct). Or you could say "we could complete a fix-point math calculation - for example -, cross-check it, and assume we've achieved 100%". Both views are interesting in my opinion. Personally, I would like to know we've achieved the later just because of the challenge. Right now, assuming no hardware, programming, cosmic errors, we know we dont do 100% (or maybe we do).

Last fiddled with by 6pac on 2018-01-27 at 21:28
6pac is offline   Reply With Quote
Old 2018-01-27, 21:15   #10
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dartmouth NS

2·3·23·61 Posts
Default

Quote:
Originally Posted by 6pac View Post
I see what you mean. I guess there is two possible views on that. You could be a nazi (for lack of better term) and say "because of say, cosmic rays, 100% is not doable". Or you could say "we could complete a fix-point math calculation - for example -, cross-check it because of cosmic rays, and assume we've achieved 100%". Both views are interesting in my opinion. Personally, I would like to know we've achieved the later.
The main problem is not many properties , except being prime are forced on the exponents that allow mersenne primes. Also because we can't deal with huge numbers well, its not as simple as starting from a known mersenne prime exponents end point. Until something is proved about what prime exponents, can give an all 0 result in general, the best thing to do is keep checking exponents.
science_man_88 is offline   Reply With Quote
Old 2018-01-27, 21:41   #11
6pac
 
Jan 2018

516 Posts
Default

Quote:
Originally Posted by science_man_88 View Post
The main problem is not many properties , except being prime are forced on the exponents that allow mersenne primes. Also because we can't deal with huge numbers well, its not as simple as starting from a known mersenne prime exponents end point. Until something is proved about what prime exponents, can give an all 0 result in general, the best thing to do is keep checking exponents.
An idea (if I understand correctly though) would be to get a candidate with floating-point math and just for the fun, try to get "100% certainty" on it using a second pass.

Last fiddled with by 6pac on 2018-01-27 at 21:43
6pac is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Double checking gd_barnes Riesel Prime Search 71 2022-10-02 17:21
Double Checking on GPU72 bayanne GPU to 72 17 2013-12-25 18:16
What about double-checking TF/P-1? 137ben PrimeNet 6 2012-03-13 04:01
Double checking Unregistered Information & Answers 19 2011-07-29 09:57
Double Checking Factors eepiccolo Software 6 2003-03-10 05:01

All times are UTC. The time now is 12:01.


Fri Jan 27 12:01:33 UTC 2023 up 162 days, 9:30, 0 users, load averages: 1.23, 1.34, 1.31

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

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