Post Reply 
50g: an interesting RAND anomaly
03-18-2018, 02:03 AM
Post: #9
RE: 50g: an interesting RAND anomaly
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.
Find all posts by this user
Quote this message in a reply
Post Reply 


Messages In This Thread
50g: an interesting RAND anomaly - DavidM - 03-17-2018, 05:02 PM
RE: 50g: an interesting RAND anomaly - ttw - 03-18-2018 02:03 AM
RE: 50g: an interesting RAND anomaly - ttw - 03-19-2018, 06:31 PM
RE: 50g: an interesting RAND anomaly - ttw - 03-19-2018, 07:35 PM



User(s) browsing this thread: