Information on calculator Random Number Generators from PPC Journal articles

[Dieter]

(11-12-2016 10:19 AM)Namir Wrote:  I tested the frac(9821x+0.211327) PRNG. I tested generating sets of 10,000 random numbers. The mean and standard deviation are close to theoretical values.

Sure. This actually is a (variation of a) simple linear congruential random number generator (LCG). It is equivalent to

(9821x + 211327) mod 10^6

and thus implements the standard LCG formula

(a·x + c) mod m

where a = 9821, c = 211327 and m = 10^6.

The HP generator returns x/m, i.e. the random result scaled to the interval [0; 1[.

It has been proven that LCGs will reach a period of m if some restrictions for a, c and m are observed: First, a and c must be relatively prime, then a–1 must be divisible by all prime factors of m, and finally if m can be divided by 4, this also has to be true for a–1.

These three conditions apply here, so the RNG has a period of 10^6. After 10^6 iterations it will have cycled through every single value from 0 to 999999, and each one occured exactly once. In other words, after 10^6 iterations (or an integer multiple of this) the variance is exactly 1/12 and the mean is exactly 1/2 (well, 1/2 – 5E–7 to be precise, since the largest possible RN is 0.999999).

(11-12-2016 10:19 AM)Namir Wrote:  The auto-correlations for the first 100 lags have absolute values less than 0.03. The histograms for the distribution of the generated numbers, in bins of 0.1 in width, have a low Chi-Square values in the range of about 3 to 9.

After 10^6 iterations every bin will hold exactly 10^5 random numbers, so the Chi² value is exactly zero. Yes, I have tried this in Excel. ;-)

This generator returns 6-digit RNs, which allows a four-digit value for a. With a different choice of the LCG parameters, especially a lower a-value, more digits and a larger period can be achieved. For 8 digits, m becomes 10^8 which, like other powers of ten, has 2 and 5 as its prime factors. Since also m can be divided by 4, both conditions combined mean that a must be 20·k+1, i.e. 21, 41, 61, 81, 121, ... Finally choosing a value for c is easy – simply take an n-digit prime.

So a possible LCGs with period 10^8 can be

(41·x + 12345701) mod 10^8

Here the value for a has to be small enough that a·x+c can be evaluated exactly with 10 digit precision.

So designing an LCG with a certain period and (finally) exact mean and variance is simple. But does this mean they are all equally good in terms of other criteria? Do they all pass the usual tests? This question has to be answered by others. ;-)

Dieter