50g: an interesting RAND anomaly

[Thomas Okken]

(03-17-2018 05:02 PM)DavidM Wrote:  Consider the following RPL program, which produces a list of 200 pseudo-random integers in the range 0..3:

Code:

\<<
  1 200 START
    RAND 1E12 * IP
    4 MOD R\->I
    RAND RAND DROP2
  NEXT
  200 \->LIST
\>>

The method used may seem a bit strange, but it's the simplest stripped-down UserRPL equivalent to the actual algorithm I'm using that I could put together. The original is actually a Saturn code object, so it uses integer math instead of floating point for performance reasons. The original also does some safety checks to make sure that the seed is in an acceptable range, but that wasn't needed for this demonstration. R→I is the only optional command here, and is simply used to make the final list easier to view.

In particular, what initially caused me to take notice of the result is that it has an interesting property: each possible number occurs exactly 50 times. I thought that was odd enough, but further investigation showed something else: running the above program repeatedly will always give exactly the same result list, provided there are no intermediate calls to RAND made. Calling RAND in between invocations will cause the result list to change, but it still repeats if the program is called repeatedly (and it still has a perfect distribution). Changing the loop count to any number that is a multiple of 200 has shown similar results, so it appears that a cycle of 600 RAND invocations is pertinent.

I also noted that changing the MOD value to 2 or 8 had similar results, but no other power of 2 I tried did.

This represents a much smaller cycle than I had expected for RAND used in this manner, though it seems to be specific to these parameters. I haven't seen similar results outside of those mentioned (yet ).

The RNG in question is documented here: https://groups.google.com/forum/m/#!msg/...tzMtZhlGoJ

It multiplies the seed by a large prime and takes the redult modulo 1e15, and then cuts off the least significant three digits from that, divides it by 1e15, and returns that. Note there's no additive constant.

In multiplying the seed by the prime, the least significant n digits of the seed are completely determined by the least significant n digits of the previous seed, and the least significant n digits of the prime factor. Looking at the least significant 2 bits of the seed-without-its-least-significant-three-digits thus gives a maximum cycle of 4000, and in practice it'll be less because not all of those 4000 values are covered by any combination of starting seed and prime.

TL;DR: if you want a random integer between 0 and 3 inclusive, do RAND 4 * IP for maximum cycle length. Stay away from the least significant digits!