50g: an interesting RAND anomaly

[ttw]

For Lehmer type generator in base 2 (the most usual and useful case) there are several interesting properties that explain some of this. For a full-length generator (like X(j+1)=41309*X(j)+1 (or any other odd number) modulo 65535, one has that the last bit (1's) alternating between 1 and 0; the second (2's ) bit having a cycle of 4, the third (8's) a cycle of 8, etc. Thus the entire system has a cycle of 2^16. This may be bad (if just using low bits) but the analysis shows one how to do well. One can take a large (256 bit or longer modulus) and use the leading bits and throw away the lower bits. For example one could imitate a 16 bit generator using a 256 bit generator and discarding the last 240 bits (a bit wasteful or maybe 240 bits wasteful) and the resulting 32 bits will have a cycle of 2^256 with the lowest bit having a cycle of 2^241 instead of 2^0.

I'm guessing that powers of other primes behave similarly. It is known (see Knuth vol2) which is the product of the cycles of the various P^k bit generators that make up the sequence.