Speeding up double checking when first test returns "prime"

[Xyzzy]

I'm surprised the residue every one million iterations isn't saved on the server.

If I'm doing a double check, and the residues don't match when I check in progress at each million iterations, I'd like to know. Maybe my box is whacked? Or maybe the previous submitter's box has a history of bad results?

The amount of storage space to save this would be trivial.

Originally Posted by Xyzzy

I'm surprised the residue every one million iterations isn't saved on the server.

I presume you mean the Res64, i.e. the bottom 64 bits of the full-length residue? Indeed, that would seem a fairly tractable thing to store. That would give us a quick way to determine whether a triple-check will be required. If one is started, the server can decide what to do based on the first checkpoint Res64 returned by the 3rd run - if it matches the DC run, continue both, if it matches the 1st-time-test, discontinue the DC run and continue with the 3rd run - seems like an excellent suggestion, but again, I wonder if the work saved would be worth the implementational cost and the risk of introducing new bugs into the server assignment-management end of things.

[axn]

Originally Posted by cheesehead

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

Yes! So?!

Originally Posted by cheesehead

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.

Yes, again. Delete them once the test is done (just like the p,q,r files). Let's say this needs 100 MB of storage (10 interims, 10 MB each). I wouldn't call that big by today's standards. And once the test is done and shown to be composite, these would be deleted anyway. So a HT m/c with two copies of Prime95 would need 200MB max -- still no biggie (according to me).

Originally Posted by cheesehead

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.

Why? Doublechecks are not the focus, verification runs are! And besides, doublechecks need nothing more than 64 bit residues, not the whole checkpoint!

Originally Posted by cheesehead

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.

You are calculating the cost for your own schemes, not what OP said (for that matter I am also calculating my own scheme, but I think it is closer in spirit to OP).

Originally Posted by cheesehead

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

LL is a deterministic test - and even when you split it up, it is still deterministic. As far as likelihood of error is concerned, there are three things to remember: 1) split-up tests will be faster, hence we can re-run them quicker in case of error 2) split-up tests will identify errors quicker and pin-point the interval in which error occurred and 3) we are still talking about prime-verification, not double checking.

Originally Posted by cheesehead

(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?

Already answered regarding the cost. Maybe you disagree about the cost of 10 files. How about the cost of one file? Even that would be tremendously helpful, wouldn't it?

Originally Posted by ewmayer

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.

Automation? Probably unnecessary. But even if needed, shouldn't be too difficult.
Agreed that this scheme would not be suitable for routine double checks, but for prime verification? And, so what if we have dedicated multi-cpu hardware? There is no such thing as "fast enough" prime verification (at least it doesn't feel like it when you are waiting "5 whole days" for the answer). Often we have multiple multi-cpu machines at our disposal, and this would make use of them for even faster verification. Heck, even if you have only one multi-cpu machine, wouldn't it be faster if each cpu got its slice of iterations than doing a multi-threaded FFT (linear speed-up vs sub-linear speedup)?


Anyways, doesn't Prime95 already store some checkpoint file for last 1000 iteration or so in case of a prime (which George reruns to see if it's a false positive)? This would be merely an extension, wouldn't it?

[cheesehead]

Originally Posted by axn1

Yes! So?!

First let me say that in my 23 Feb posting I was not careful to clearly delineate between what I wrote relevant to verification versus what was relevant to doublechecking.

The "so" is that a measure intended for helping only verification would impose overhead on all testers even though it would be useful only for the < 0.001% of the time when a prime is reported. In order to justify this 100,000-fold overkill, it seems to me that there should be extraordinary benefits for that 0.001% of the time it's used.

Or else there needs to be some benefit for doublechecking in the other 99.999%+ cases.

Yes, again. Delete them once the test is done (just like the p,q,r files). Let's say this needs 100 MB of storage (10 interims, 10 MB each). I wouldn't call that big by today's standards.

But the problem (in justifying the overhead) here is the small fraction of systems where the extra 100 MB does cause trouble. Again -- where's the benefit to justify that? All I see is that some people are too impatient to wait a few days for a verification; letting them practice patience won't screw up anyone's system.

So a HT m/c with two copies of Prime95 would need 200MB max -- still no biggie (according to me).

And waiting the few days for verification is, to me, no biggie either.

Doublechecks are not the focus, verification runs are!

I regret not having made it clearer that I already understood this to be the OP's focus.

And besides, doublechecks need nothing more than 64 bit residues, not the whole checkpoint!

If you're going to split doublechecking nonduplicatively onto N different systems, then N-1 of them have to start from a complete checkpoint file, not just a residue.

You are calculating the cost for your own schemes, not what OP said

... because, as I previously indicated, the OP failed to consider (or, at least, to mention) all the relevant costs that will be required to implement his scheme.

LL is a deterministic test - and even when you split it up, it is still deterministic.

Mathematically, yes. But real-world computing is not perfect -- thus the intrusion of error considerations.

As far as likelihood of error is concerned, there are three things to remember: 1) split-up tests will be faster, hence we can re-run them quicker in case of error

But splitting-up increases the complexity of detecting errors, which is prerequisite to those re-runs.

Explain to me again why it's so vitally important to cut a few days off the once-a-year-or-so verification of a prime, to justify the added complexity.

2) split-up tests will identify errors quicker and pin-point the interval in which error occurred

Explain to me again ...

3) we are still talking about prime-verification, not double checking.

So since you're not concerned about benefits to DC, that only focuses your burden on showing why the few-days speedup of verification is worth the added complexity of splitting it up.

Maybe you disagree about the cost of 10 files. How about the cost of one file? Even that would be tremendously helpful, wouldn't it?

No, not tremendously.

(Explain to ...)

Agreed that this scheme would not be suitable for routine double checks, but for prime verification?

If it's not suitable for routine DC, why is it suitable for a prime verification DC?

And, so what if we have dedicated multi-cpu hardware? There is no such thing as "fast enough" prime verification (at least it doesn't feel like it when you are waiting "5 whole days" for the answer).

So here we have the crux of the matter:

some folks' impatience

[ewmayer]

Originally Posted by cheesehead

If you're going to split doublechecking nonduplicatively onto N different systems, then N-1 of them have to start from a complete checkpoint file, not just a residue.

Small point of clarification: mathematically speaking, a "residue" means the entire mod-M(p) LL-test iterate, i.e. implies the contents of a complete multi-megabyte checkpoint file. What you're referring to above is the least-significant 64 bits of the residue, i.e. the 'Res64' in GIMPS terminology.

So here we have the crux of the matter:

some folks' impatience

Yep - primality testing, meet Grand Theft Auto.

[cheesehead]

Originally Posted by ewmayer

Small point of clarification: mathematically speaking, a "residue" means the entire mod-M(p) LL-test iterate, i.e. implies the contents of a complete multi-megabyte checkpoint file. What you're referring to above is the least-significant 64 bits of the residue, i.e. the 'Res64' in GIMPS terminology.

Yes. Thank you. I forgot this when interpreting the original posting. I have indeed been thinking "residue" means "Res64", and thus may have confused this discussion with my (incorrect) distinction between "checkpoint file" and "residue". I apologize to all.