Getting reliable LL from unreliable hardware

[error]

Originally Posted by preda

No, I simply don't know how to do it -- I'm lacking the math background. If you could describe how to do it, that'd help me understand.

Ah, OK. See https://en.wikipedia.org/wiki/Jacobi_symbol

Basically you check the numbers mod 4 or 8, swap them around, take the remainder, and repeat until you end up with 1 or 2.

[preda]

Originally Posted by error

Ah, OK. See https://en.wikipedia.org/wiki/Jacobi_symbol

Basically you check the numbers mod 4 or 8, swap them around, take the remainder, and repeat until you end up with 1 or 2.

OK, reading the wikipedia article I see there's a fast way to compute the Jacobi symbol.

I have two more questions:

- why, if R is a valid LL residue, (R-2/Mp) must be -1.
- why, if (x-2/Mp) is 1, it follows that iterating LL from x produces (R-2/Mp)==1 at each iteration.

(if I understood correctly what you said).

[error]

Originally Posted by preda

OK, reading the wikipedia article I see there's a fast way to compute the Jacobi symbol.

I have two more questions:

- why, if R is a valid LL residue, (R-2/Mp) must be -1.
- why, if (x-2/Mp) is 1, it follows that iterating LL from x produces (R-2/Mp)==1 at each iteration.

(if I understood correctly what you said).

At the beginning R0 = 4

This is always (R0+2/Mp) = -1 and (R0-2/Mp) = 1

The next residue is R1 = R0^2-2

This computes as (R1+2/Mp) = (R0^2/Mp) = 1 and (R1-2/Mp) = (R0^2-4/Mp) = ((R0-2)(R0+2)/Mp) = (R0-2/Mp)(R0+2/Mp) = 1*(-1) = -1

For any subsequent iteration the same happens: (Ri+2/Mp) = 1 and (Ri-2/Mp) = -1

If you take a random number Rx instead, it has equal probabilities of having any of the four combinations of (Rx+-2/Mp) as ++, +-, -+, --(1)

Then computing ((Rx^2-2)+-2/Mp) would result in ++, +-, +-, ++, which is wrong to be a proper residue 50% of the cases (it should be +-).

If you could check this at every iteration, i.e. also when you happen to run into Rx, you'd catch the case -+ as well, so 75% of the cases, and only +- would let you continue.

[preda]

Originally Posted by error

At the beginning R0 = 4

This is always (R0+2/Mp) = -1 and (R0-2/Mp) = 1

The next residue is R1 = R0^2-2

This computes as (R1+2/Mp) = (R0^2/Mp) = 1 and (R1-2/Mp) = (R0^2-4/Mp) = ((R0-2)(R0+2)/Mp) = (R0-2/Mp)(R0+2/Mp) = 1*(-1) = -1

For any subsequent iteration the same happens: (Ri+2/Mp) = 1 and (Ri-2/Mp) = -1

If you take a random number Rx instead, it has equal probabilities of having any of the four combinations of (Rx+-2/Mp) as ++, +-, -+, --(1)

Then computing ((Rx^2-2)+-2/Mp) would result in ++, +-, +-, ++, which is wrong to be a proper residue 50% of the cases (it should be +-).

If you could check this at every iteration, i.e. also when you happen to run into Rx, you'd catch the case -+ as well, so 75% of the cases, and only +- would let you continue.

Indeed -- thanks! This sounds like a useful inexpensive characteristic to check. Probably not practical to check on each iteration, but even done per "block" (e.g. 10K iterations) should catch 50% of 1-errors, and get better for multi-errors. Cool!

[retina]

How does this differ from the sum_of_inputs = sum_of_outputs test? Is it more robust? It is cheaper to compute? Should it be used as an additional test or a replacement? If there are two (or more) errors that occur between doing the tests does it go back to the +- result?

[error]

Originally Posted by retina

How does this differ from the sum_of_inputs = sum_of_outputs test? Is it more robust? It is cheaper to compute? Should it be used as an additional test or a replacement? If there are two (or more) errors that occur between doing the tests does it go back to the +- result?

If I understand that right, sumin = sumout check can only find errors in one individual iteration, where it is made.

"Jacobi-flip" sustains in subsequent iterations as well.

If more than one random errors occur in between, you gain no more, as these have an equal chance of curing the improper value as keeping it such. The overall chance remains at 50%.

[preda]

Originally Posted by retina

How does this differ from the sum_of_inputs = sum_of_outputs test? Is it more robust? It is cheaper to compute? Should it be used as an additional test or a replacement? If there are two (or more) errors that occur between doing the tests does it go back to the +- result?

I have limited knowledge about sum_inp^2 != sum_out, but this is about what I remember:
- the sumout is huge, so care ("tricks") must be taken when doing the summation otherwise the errors overcome the signal.
- the sums are not over integers, but over the reals produced by the weighting of the DWT (or the output of the IFFT, before the reverse weighting)
- there is an heuristic element in deciding how much difference is "too much" (i.e. the test is approximate)

In practice, on GPU at least, the "max error" seems to me an easier and more useful indication of a plausible result.

About the "sticky" behavior of the Jacobian test, my intuition is this: when checking after each batch (e.g. 10K iterations), if inside the batch there is one *or more* errors, there is 50% probability of detection at the batch level.

So if over the whole LL there are E errors, if E is much smaller than the number of batches, we have overall "undetected error" of 0.5^E. The worst case would still be a single error (over the whole LL) with overall detection of only 1/2.

[preda]

Computing the Jacobi symbol is not so fast after all -- the slow operation is the repeated modulo of big integers. I did some experiments with GMP (GNU MP) which conveniently offers mpz_jacobi(), and the time for exponent 77002949 is around 55s on one core of my CPU.

Everything works as expected otherwise, producing -1 on all iterations.

[Prime95]

Originally Posted by preda

Computing the Jacobi symbol is not so fast after all -- the slow operation is the repeated modulo of big integers. I did some experiments with GMP (GNU MP) which conveniently offers mpz_jacobi(), and the time for exponent 77002949 is around 55s on one core of my CPU.

Everything works as expected otherwise, producing -1 on all iterations.

55 seconds every ten or hundred thousand iterations for a 50% chance of discovering an error seems like pretty cheap insurance to me.

Is there free Jacobi code available ( GMP has poisonous GNU license restrictions )? P.S. I'd google for free code but my Internet availability is severely restricted at the moment. P.P.S. I think using libgmp would avoid license issues assuming one can freely ship libgmp for all platforms that prime95 supports. But then again IANAL.

[GP2]

Originally Posted by Prime95

P.P.S. I think using libgmp would avoid license issues assuming one can freely ship libgmp for all platforms that prime95 supports. But then again IANAL.

For Windows there's a compatible library called MPIR which is licensed LGPL v3+. Is that an acceptable license?

[chalsall]

Originally Posted by GP2

...which is licensed LGPL v3+. Is that an acceptable license?

It should be. The GNU Lesser General Public License allows inclusion of the code into proprietary software.