2020-11-01, 19:33 | #1 |
"Robert Gerbicz"
Oct 2005
Hungary
5FB_{16} Posts |
Better error correction
With a probably restarted computation the task is to compute base^(2^n) mod N, so here we can have that base is "big". As usual the standard setup, let:
x[t]=base^(2^(t*L)) mod N y[t]=x[0]*x[1]*..*x[t] mod N then: we compute the y[] sequence with y[t]=y[t-1]*x[t] the error check: y[t]=base*y[t-1]^(2^L) mod N should hold. If we have a detected error for t=m, but we have stored in memory (x[t],y[t-1],y[t]) earlier residues for 0<t<m then we can find the largest t where we have an error checked residue with a binary search [it can be t=0 if we have no positive t], and continue the work with that stored x[u],y[u] that is passing the error check. Ofcourse with no failure it gives no speedup but quicker regain when we have error(s), because you can save some iterations where we're almost absolutely sure that the work was correct. Assuming there was a single error we'll save on average (at most) half of the residues. It would be worth to use say 8 (or more) such stored (x[t],y[t-1],y[t]) residues if the cpu/gpu memory still allows [with equally spaced t=m/8*i for i=1..8, note that for t=0 we have an error checked residue], probably less if we are still in the P-1 1st phase's iterations since that is also a memory hungry job. Notice that it is really worth because one (strong) error check takes L multiplications so a full binary search takes only extra log2(8)*L=3*L multiplications [for 8 stored triplets], but we can save up to L*m iterations. Storing too many triplets is pointless, even if memory allows that since copying residues takes time. ps. It is not need to store the intermediate x[t], because for a strong checked point: x[t]=y[t]/y[t-1] mod N. Last fiddled with by R. Gerbicz on 2020-11-01 at 19:41 Reason: trivial typo |
Thread Tools | |
Similar Threads | ||||
Thread | Thread Starter | Forum | Replies | Last Post |
Pointwise error correction of convolution outputs | ewmayer | Math | 1 | 2019-12-05 00:16 |
Mersenne software error detection or correction opportunities | kriesel | Software | 6 | 2018-08-06 21:15 |
@ Supermods: Error Correction please | Raman | Forum Feedback | 72 | 2013-06-22 07:24 |
Prime Density Correction Terms? | wblipp | Math | 20 | 2011-09-07 21:45 |
Error 5 causes userid change and error 17 updates for exponents | Old man PrimeNet | PrimeNet | 0 | 2006-02-05 02:27 |