50g: an interesting RAND anomaly
03-18-2018, 02:03 AM
Post: #9
 ttw Member Posts: 248 Joined: Jun 2014
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.
 « Next Oldest | Next Newest »

 Messages In This Thread 50g: an interesting RAND anomaly - DavidM - 03-17-2018, 05:02 PM RE: 50g: an interesting RAND anomaly - J-F Garnier - 03-17-2018, 05:43 PM RE: 50g: an interesting RAND anomaly - DavidM - 03-17-2018, 06:13 PM RE: 50g: an interesting RAND anomaly - Claudio L. - 03-17-2018, 06:41 PM RE: 50g: an interesting RAND anomaly - DavidM - 03-17-2018, 07:38 PM RE: 50g: an interesting RAND anomaly - John Keith - 03-17-2018, 09:17 PM RE: 50g: an interesting RAND anomaly - DavidM - 03-17-2018, 10:23 PM RE: 50g: an interesting RAND anomaly - pier4r - 03-17-2018, 10:43 PM RE: 50g: an interesting RAND anomaly - ttw - 03-18-2018 02:03 AM RE: 50g: an interesting RAND anomaly - Thomas Okken - 03-18-2018, 03:44 AM RE: 50g: an interesting RAND anomaly - DavidM - 03-18-2018, 04:08 PM RE: 50g: an interesting RAND anomaly - Paul Dale - 03-18-2018, 10:52 PM RE: 50g: an interesting RAND anomaly - John Keith - 03-19-2018, 02:23 PM RE: 50g: an interesting RAND anomaly - DavidM - 03-19-2018, 02:57 PM RE: 50g: an interesting RAND anomaly - pier4r - 03-19-2018, 03:04 PM RE: 50g: an interesting RAND anomaly - DavidM - 03-19-2018, 03:26 PM RE: 50g: an interesting RAND anomaly - ttw - 03-19-2018, 06:31 PM RE: 50g: an interesting RAND anomaly - pier4r - 03-19-2018, 07:08 PM RE: 50g: an interesting RAND anomaly - ttw - 03-19-2018, 07:35 PM RE: 50g: an interesting RAND anomaly - cyrille de brĂ©bisson - 03-20-2018, 06:03 AM RE: 50g: an interesting RAND anomaly - Joe Horn - 03-20-2018, 05:47 PM RE: 50g: an interesting RAND anomaly - DavidM - 03-21-2018, 02:10 AM