Another thought struck me - this could have useful applications in L-L 
testing programs.

If M is the Mersenne number being tested & R(i) is the L-L residue after i 
iterations, then
R(i+1) = R(i) * R(i) - 2 (modulo M) (by the statement of the L-L algorithm)

But note that (M - R(i))^2 - 2 = M^2 - 2MR(i) + R(i)^2 - 2
so (M-R(i))^2 - 2 (modulo M) is clearly equal to R(i+1).

How can this be of any use? Well, when we have a dubious iteration (say an 
excessive roundoff or sum error) we can check the output by redoing the last 
iteration but starting from (M-R(i)) instead of R(i) - the output should be 
the same. Furthermore the action of calculating M-R(i) is very easy - just 
invert all the bits.

Also, if we have suspicions about the accuracy of code when there is a high 
density of 1 bits, we can try just one iteration but starting at M-4 instead 
of 4. The output residual should be 14 irrespective of M (providing M>7 - as 
will often be the case!). The point here is that, just as the value 4 is 
represented by a string of p bits only one of which is set, M-4 is 
represented by a string of p bits only one of which is unset.

Brian Beesley
Unsubscribe & list info -- http://www.ndatech.com/mersenne/signup.htm
Mersenne Prime FAQ      -- http://www.tasam.com/~lrwiman/FAQ-mers

Reply via email to