Speeding up double checking when first test returns "prime"

2006-02-22, 05:39

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.)

Uncwilly · 2006-02-22, 07:10

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.

cheesehead · 2006-02-22, 07:20

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. :-)

axn · 2006-02-22, 19:52

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.

Uncwilly · 2006-02-23, 00:19

Quote:

Originally Posted by Uncwilly

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

.

philmoore · 2006-02-23, 00:31

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.

JuanTutors · 2006-02-23, 01:48

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.

jinydu · 2006-02-23, 01:59

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.

cheesehead · 2006-02-23, 08:47

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?

smh · 2006-02-23, 10:55

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

ewmayer · 2006-02-23, 17:33

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.

2006-02-22, 05:39	#1
Unregistered 3⁴·7² Posts	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.)

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

2006-02-22, 07:10	#2
Uncwilly 6809 > 6502 """"""""""""""""""" Aug 2003 101×103 Posts 3²×5²×7² Posts	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.

2006-02-22, 19:52	#4
axn Jun 2003 43·127 Posts	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.

2006-02-23, 00:31	#6
philmoore "Phil" Sep 2002 Tracktown, U.S.A. 19×59 Posts	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.

2006-02-23, 01:48	#7
JuanTutors "Juan Tutors" Mar 2004 571₁₀ Posts	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.

2006-02-23, 01:59	#8
jinydu Dec 2003 Hopefully Near M48 6DE₁₆ Posts	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.

2006-02-23, 17:33	#11
ewmayer ∂²ω=0 Sep 2002 República de California 2²·2,939 Posts	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.