[EDIT: This post was revised on September 16, 2012 because the LMD3
code was right, but this documentation was wrong.]
LMD3 was introduced informally in the
previous post. It is not indended to be used as an error detection algo, unless you're more interested in long nonzero sequences than maximimizing double-bit error detection coverage length. For the latter,
LMD2 still serves its purpose.
Alternatively, LMD3 can supplement LMD2, if you're paranoid and want to use a 128-bit EDC. In such a regime, 64-bit pseudorandom numbers can be rapidly generated, by concatenating the "x" values of LMD2 and LMD3. (Remember, "c" is not considered part of the pseudorandom output; it's just present to prevent "x" from behaving too predictably.) A smooth transition between 32 and 64 bits can occur.
Let me explain. I happen to be working on an unrelated algo at the moment, which requires that 32-bit pseudorandom numbers be used. However, when the data volume reaches a critical point, 32 bits is no longer enough; I need 64 bits. The problem is that I need a relatively smooth transition between the two, such that the 32-bit fraction at iteration "n" is very close to the 64-bit fraction at iteration "n". Otherwise, the transition would be awkward to the user, in the sense that the program's behavior would be radically different.
So, for instance, if one of the pseudorandom values is 0x8D903EE7 in the first sequence, then a compatible value would be, say, 0x8D903EE79CA4B29B. If we look at these values as fractions on [0,1), then as you can see, the second fraction is within 1 part in 2^32 of the first, which constitutes a smooth transition within the limits of 32-bit precision.
One could do this using any 2 32-bit pseudorandom sequences. But we want the high and low parts to be uncorrelated, yet rapidly generated without the need to compute 128-bit products. Double use of LMD2_A (0xFE001000) helps in this regard.
LMD3 has the seeds that it has because it caters to the cases wherein one is more concerned with long nonzero sequences than double-bit coverage. But if used in the manner above, then it can also provide a smooth (and fast) transition between 32-bit and 64-bit sequences. Granted, because the multipier is still LMD2_A, the period of the resulting sequence is the same as for LMD2, regardless of whether LMD2 and LMD3 are combined. For practical applications, this probably doesn't matter. This could be avoided by using a different multiplier, for example, 0xF7FBFFFF, which is only slightly slower than LMD2_A.
Following is the definition of LMD3. Note that it behaves exactly like LMD2, except for the seeds:
ITERATE_NO_ZERO_CHECK means:
p = 0xFE001000 * x + c
x <- p MOD 2^32
c <- p / 2^32 (Shift p right by 32.)
(x0, c0) = (0x0, 0xDA6D32BA)
(That's not a typo. "x" should rightly start at 0 in order to maximize the number of subsequent nonzero terms.)
Thus:
(x1, c1) = (0xDA6D32BA, 0x0)
(x2, c2) = (0x5F2BA000, 0xD8B865FB)
(x3, c3) = (0x92B865FB, 0x5E6D4EB3)
Thus:
(LMD3 of null) = 0x38DA816D92B865FB
If what you really want is a pseudorandom sequence with a period roughly the square as long, then LMD3 will not help you. Instead, try combining LMD2 with a sequence using the multiplier 0xF7FBFFFF:
0xF7FBFFFF * x = (x * 2^32) - (x * 2^27) - (x * 2^18) - x
As required, (0xF7FBFFFF * 2^32 - 1) and (0xF7FBFFFF * 2^31 - 1) are both prime. The cycle length (in the absence of LMD2) is the latter, or 8,934,578,708,602,159,103, which is enough 32-bit "x" values to exceed the size of a 64-bit address space. Because LMD2 and this new sequence have prime and unequal cycle lengths, the cycle length of their concatenated "x" values is the product of their cycle lengths, or 81,763,217,765,900,274,931,684,699,996,617,179,137, which is just under 2^126.
And finally, just because I happened to take the time to compute it: if a long nonzero initial sequence is what you want, then try the following with 0xF7FBFFFF:
It will produce 44,342,898,605 nonzero values, starting with the output of the first iteration.
