mersenneforum.org  

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

Reply
 
Thread Tools
Old 2006-02-22, 05:39   #1
Unregistered
 

302810 Posts
Default Speeding up double checking when first test returns "prime"

Suppose Mp is tested the first time and Prime95 says Mp is prime. Wouldn't it speed up double checking tremendously if, say, 10 or so interim residues had been saved, and the double checking is done by distributing those 10 residues? to 10 different computers? (So one computer does the first 1/10th of the double checking while a second computer does the second 1/10th of the double checking, etc.)
  Reply With Quote
Old 2006-02-22, 07:10   #2
Uncwilly
6809 > 6502
 
Uncwilly's Avatar
 
"""""""""""""""""""
Aug 2003
101×103 Posts

26×32×17 Posts
Default

You still need an independant "different hardware and different software" run, from start to finish.

Testing the save files is a nice idea to have more confidance, but many users would not want all those files on their machine, especially as they are generally unneeded. The current system (described elsewhere) is fine.
Uncwilly is offline   Reply With Quote
Old 2006-02-22, 07:20   #3
cheesehead
 
cheesehead's Avatar
 
"Richard B. Woods"
Aug 2002
Wisconsin USA

22×3×641 Posts
Default

Quote:
Originally Posted by Unregistered
Wouldn't it speed up double checking tremendously if, say, 10 or so interim residues had been saved, and the double checking is done by distributing those 10 residues? to 10 different computers?
Sure ... if everything works perfectly the way it's supposed to.

But the reason for doublechecking is precisely because not everything works perfectly.

By introducing the complications of generating, storing, and transmitting (usually twice) N (N = 10 in your example) multimegabyte checkpoint data files (you can't just limit this to short residues -- each partial computation except the first has to start from a complete checkpoint file, and the first doublechecker has to transmit its checkpoint file for comparison), having to make N result file comparisons, and so on, this would greatly increase the possibilities of introducing errors.

Also, this scheme would impose the extra burden of storing N-1 intermediate checkpoint files on every GIMPS participant, 99.99+% of whom will not be finding a prime.

But -- thanks for trying to help with your suggestion. :-)

Last fiddled with by cheesehead on 2006-02-22 at 07:25
cheesehead is offline   Reply With Quote
Old 2006-02-22, 19:52   #4
axn
 
axn's Avatar
 
Jun 2003

507610 Posts
Default

The OP says to use this only when Prime95 says prime -- not for composites. And the purpose would be to speed up the verification runs -- not for ordinary doule checks. It's actually a great idea. In fact a _single_ halfway checkpoint would potentially halve the verification time.
axn is offline   Reply With Quote
Old 2006-02-23, 00:19   #5
Uncwilly
6809 > 6502
 
Uncwilly's Avatar
 
"""""""""""""""""""
Aug 2003
101×103 Posts

26×32×17 Posts
Default

Quote:
Originally Posted by Uncwilly
You still need an independant "different hardware and different software" run, from start to finish.
.
Uncwilly is offline   Reply With Quote
Old 2006-02-23, 00:31   #6
philmoore
 
philmoore's Avatar
 
"Phil"
Sep 2002
Tracktown, U.S.A.

111910 Posts
Default

But just because the save-files were generated by one program doesn't mean that they can't be used for a "different hardware, different software" verification. I think the idea has a lot of merit, particularly as tests get longer and longer.
philmoore is offline   Reply With Quote
Old 2006-02-23, 01:48   #7
JuanTutors
 
JuanTutors's Avatar
 
Mar 2004

21C16 Posts
Default

I think it would be good to speed up verification runs of a positive result. Knowing if a double check returned "prime" three days later would be nice, even if we are waiting a few weeks for some completely different software to do a full double check on completely different hardware.
JuanTutors is offline   Reply With Quote
Old 2006-02-23, 01:59   #8
jinydu
 
jinydu's Avatar
 
Dec 2003
Hopefully Near M48

175810 Posts
Default

Another advantage of this idea is that it would make it much harder for an unscrupulous user to request both an exponent and its double-check.
jinydu is offline   Reply With Quote
Old 2006-02-23, 08:47   #9
cheesehead
 
cheesehead's Avatar
 
"Richard B. Woods"
Aug 2002
Wisconsin USA

22·3·641 Posts
Default

Quote:
Originally Posted by axn1
The OP says to use this only when Prime95 says prime -- not for composites.
But the OP didn't realize, or overlooked, that Prime95 can't tell the difference between a composite and a prime until after it has completed all iterations.

Suppose you're 10% completed (using the OP's N=10). If the result is going to be prime, then it's time to write an interim checkpoint file, but if the result's not going to be prime, Prime95 can skip that. How does Prime95 decide whether to write the file, without using a crystal ball?

Answer: it can't, so it has to write all the interim files every time, composite or prime! :-)

Of course, one can choose not to transmit them if they're not going to be used for doublechecks or verification, but there will still be the overhead of storing those extra files until at least the end of each run.

Quote:
And the purpose would be to speed up the verification runs -- not for ordinary doule checks.
Since you're going to have all those interim files every time, they're available for doublechecks anyway -- if there were a good reason to use them for that.

Quote:
It's actually a great idea.
But one has to weigh the costs versus the benefits ... and as far as I can see after pondering a while, this idea just doesn't have sufficient benefit to justify its cost.

Quote:
In fact a _single_ halfway checkpoint would potentially halve the verification time.
(A) But we really can't trust a verifcation unless it's flawlessly performed start-to-finish. As I've pointed out, in real life the more complicated the verification scheme (such as splitting one verification run over multiple systems), the more likely that an error will occur.

(B) Does the 0.001%, or less, chance that the extra file will be useful for verification justify imposing the extra file storage on every LL tester?
cheesehead is offline   Reply With Quote
Old 2006-02-23, 10:55   #10
smh
 
smh's Avatar
 
"Sander"
Oct 2002
52.345322,5.52471

29×41 Posts
Default

From UNDOC.TXT:
Quote:
You can have the program generate save files every n iterations. The files
will have a .XXX extension where XXX equals the current iteration divided
by n. In prime.ini enter:
InterimFiles=n
smh is offline   Reply With Quote
Old 2006-02-23, 17:33   #11
ewmayer
2ω=0
 
ewmayer's Avatar
 
Sep 2002
República de California

5·17·137 Posts
Default

The idea of having the first-time-test program deposit periodic residues, the intervals between which can then be processed in parallel by multiple slower machines, is the same kind of double-check that was used for the last few compositeness tests on Fermat numbers (F22 and F24). The problem is that automating such a procedure and managing the transfer of the residue files is a nontrivial task. Given that we're always going to need one machine (whether multiprocessor or not) to do the sequential first-time test, I don't see what the problem is with the current procedure of doing a second wave of double-checks a year or so later. In cases where the first-time test says "prime!", we have dedicated multi-CPU hardware to throw at an immediate double-check. The only problem is if the first-time test incorrectly returns a "not prime" result for a number that is actually prime - based on our current error rate that has a probability of occurring on the order of 1%. So in the worst case we don't find out that the number is prime until a year later - big deal. We're not talking about the "race for a cure" for some terrible disease here, people won't be dying as a result of that occasional first-time-test glitch.

It's always easy to say "things should be done this way" if you don't have to write the resulting code yourself, isn't it? There are extremely few people actually doing serious coding for this project, our time is limited, and as a result we have to choose our battles very carefully.
ewmayer is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
GQQ: a "deterministic" "primality" test in O(ln n)^2 Chair Zhuang Miscellaneous Math 21 2018-03-26 22:33
Checking your "bad results" status is important Madpoo Hardware 4 2015-05-15 23:25
Aouessare-El Haddouchi-Essaaidi "test": "if Mp has no factor, it is prime!" wildrabbitt Miscellaneous Math 11 2015-03-06 08:17
P-1 B1/B2 selection with "Test=" vs "Pfactor=" James Heinrich Software 2 2005-03-19 21:58
Would Minimizing "iterations between results file" may reveal "is not prime" earlier? nitai1999 Software 7 2004-08-26 18:12

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


Sun Jul 25 19:36:48 UTC 2021 up 2 days, 14:05, 0 users, load averages: 2.44, 1.89, 1.69

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