Information on calculator Random Number Generators from PPC Journal articles

[Gene]

Evaluation of many common RNGs

PPC V4N8 comments

Images of RNG output

Images


These are some of the findings that led programmers away from (Seed + PI) ^2 or ^5 etc. and into the 997 x generators of the best of all 9821 x 0.211327 + models.

[Dieter]

(11-06-2016 08:29 PM)Gene Wrote:  These are some of the findings that led programmers away from (Seed + PI) ^2 or ^5 etc. and into the 997 x generators of the best of all 9821 x 0.211327 + models.

Let's see.

• The frac(x+pi)² RNG ...has room for improvement. And frac(x+pi)³ performs somewhat better.
• The 997 generator is OK if (!) there is a suitable seed. The 7th digit should be 1, 3, 7 or 9, but even then some problems may occur.
• There seems to be an even better RNG of the same style that calculates frac(3579 x). What about that one?
• The frac(9821x+0,211327) RNG seems to be even better.
  

But maybe we should see all this a bit more relaxed – after all we are not doing serious math here, and most solutions should be OK for rolling dice. ;-)

Dieter

[Paul Dale]

Not relevant to the historic generators but the 34S uses a Tausworthe Generator. Good properties and a period around 2⁸⁸.

I would have used a Mersenne Twister but RAM was lacking.


Pauli

[Dieter]

(11-07-2016 08:06 AM)Paul Dale Wrote:  Not relevant to the historic generators but the 34S uses a Tausworthe Generator. Good properties and a period around 2⁸⁸.

That's... adequate. Especially if the result can have at most 10¹⁶ or 10³⁴ different values. #-)

But since the 34s can be equipped with a crystal: have you ever considered some kind of time-related random number generator? Could something like this have been realized?

Dieter

[Otto55]

(11-07-2016 07:33 PM)Dieter Wrote:  

(11-07-2016 08:06 AM)Paul Dale Wrote:  Not relevant to the historic generators but the 34S uses a Tausworthe Generator. Good properties and a period around 2⁸⁸.

That's... adequate. Especially if the result can have at most 10¹⁶ or 10³⁴ different values.

Not sure I got your point - do you say that's overkill?

[Dieter]

(11-07-2016 08:12 PM)Otto55 Wrote:  

(11-07-2016 07:33 PM)Dieter Wrote:  That's... adequate. Especially if the result can have at most 10¹⁶ or 10³⁴ different values.

Not sure I got your point - do you say that's overkill?

On the 34s nothing really is overkill. For this calculator it's just ...adequate. ;-)
Consider the internal precision: 39+ digits, just to make sure that the first 16 are OK.

Dieter

[Paul Dale]

(11-07-2016 07:33 PM)Dieter Wrote:  But since the 34s can be equipped with a crystal: have you ever considered some kind of time-related random number generator? Could something like this have been realized?

It would be possible to use the time as a source of entropy to feed into the random function. My feeling is that the amount and quality of entropy produced would be quite low and there would have to be a means to disable this, so the random function could be seeded to a repeatable value. Having a crystal would make things less random I suspect.

Still, there would be nothing stopping the device collecting timer readings over a period and using that as a seed for a pseudo random number generator.


Pauli

[Valentin Albillo]

 
Hi, Gene:

(11-06-2016 08:29 PM)Gene Wrote:  These are some of the findings that led programmers away from (Seed + PI) ^2 or ^5 etc. and into the 997 x generators of the best of all 9821 x 0.211327 + models.

Frankly, this 9821... is utter overkill for the stated purpose of providing some randomness to calculator games.

Back in the days of the 25C, 67, and 41, I did always use the smallest, fastest of them all, namely:

RCL 00, R-D, FRAC, STO 00

and it worked great for the stated purpose, calculator games (not statistical analysis, not Monte Carlo algorithms, etc). I sent a mini-article to PPC recommending it and remember that someone subjected it to test after test after test till he finally succeded in finding that it wouldn't pass the Spectral Test precisely, which was a foregone conclusion from the get go.

As long as you don use 0 or a multiple of Pi for the initial seed, this R-D generator saves bytes and time and provides decent results for games without quickly repeating, certainly you'll never play any of them thousands of times in a row.

Regards.
V.
 

[Gene]

And here's a link to your R-D RNG in PPC Journal V7N6:

V7N6 Valentin's R-D RNG write-up

[Dieter]

(11-07-2016 11:06 PM)Gene Wrote:  And here's a link to your R-D RNG in PPC Journal V7N6:

V7N6 Valentin's R-D RNG write-up

The text says that the seed must not be pi or an integer multiple thereof. In this case the R-D function would return a multiple of 180° and thus a fractional part of 0 – and all subsequent "random" numbers would be zero as well. But this is not the only limitation. The seed also must not be equal to any value in radians that is equivalent to 1°, 2°, 3°, ... 180°, 181°, 182°, ... . A part of these will not round to an integer angle after R-D, so these do not return 0 as the next random number, but a very small value like 1E–8 may be returned which leads to a predictable sequence of near-zero random numbers following this one.

As already mentioned in previous posts I agree with Valentin in that we should see the random number generation for this application (games) a bit more relaxed. That's why I suggested the frac(x+pi)² method. Even though it may have its weak points in terms of mathematical properties, it worked fine for me over the last decades. And it can be used even with integer. negative and zero seeds.

Dieter

[Werner]

One more problem is that Valentin's RNG does not produce the same sequence on different machines. If you start out with seed=8, Free42 and a real 42S diverge after only 6 iterations. Same for 41 vs. 42.
(I use it mainly to populate random matrices, and so I'd like to have the same pseudo-random matrix on each machine)

Cheers, Werner

[Dieter]

(11-08-2016 08:08 AM)Werner Wrote:  One more problem is that Valentin's RNG does not produce the same sequence on different machines. If you start out with seed=8, Free42 and a real 42S diverge after only 6 iterations.

Sure. That's 25 or 34 vs. 12 digits.
That's why the results will be different after the first run already: the 42s will return 0,366236105 while on Free42 it's 0,366236104655670143852...

(11-08-2016 08:08 AM)Werner Wrote:  Same for 41 vs. 42.

And here it's 10 vs. 12 digits.

(11-08-2016 08:08 AM)Werner Wrote:  (I use it mainly to populate random matrices, and so I'd like to have the same pseudo-random matrix on each machine)

Simple solution: round the result to, say, 6 places. In most cases the 10-digit calculators (41, 67, 97 etc.) will not return more than 7 or 8 digits anyway.

Dieter

[Namir]

The cycle length of a random number generator is not very relevant in the case of Calculator games since the number of iterations is relatively small. What really matters is the distribution of these random numbers. If they are of reasonably good quality then these games would play well on calculators

Namir

[Pekis]

A uniform distribution is needed: for generated numbers between 0 and 1, a mean of 1/2 is expected, as well as a variance of 1/12.

[Dieter]

(11-11-2016 08:08 PM)Pekis Wrote:  A uniform distribution is needed: for generated numbers between 0 and 1, a mean of 1/2 is expected, as well as a variance of 1/12.

This is not much of a problem, not even for the (x+pi)² generator. With 100.000 random numbers the mean is about 0,499 and the variance ~0,087. Yes, the 997 generator comes closer to 0.5 and 0,0833 – but this does not matter much for game programs.

But there are other critera that should be considered for more sophisticated applications. Take a look at the PPC Journal article Gene posted here.

Dieter

[Pekis]

(11-11-2016 09:02 PM)Dieter Wrote:  

(11-11-2016 08:08 PM)Pekis Wrote:  A uniform distribution is needed: for generated numbers between 0 and 1, a mean of 1/2 is expected, as well as a variance of 1/12.

This is not much of a problem, not even for the (x+pi)² generator. With 100.000 random numbers the mean is about 0,499 and the variance ~0,087. Yes, the 997 generator comes closer to 0.5 and 0,0833 – but this does not matter much for game programs.

But there are other critera that should be considered for more sophisticated applications. Take a look at the PPC Journal article Gene posted here.

Dieter

I didn't see any reference to the 1/12 variance in the article ... It's however the first prerequesite for a uniform distribution between 0 and 1, and it seems better saying it

[Namir]

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. 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. I think the PRNG is adequate for generating random number for calculator applications and games.

Namir

[Gene]

Namir,

Any chance you could do the same for these two RNGs ?

RCL 00
R-D
FRC
STO 00


and

RCL 00
PI
+
X^2
ST*L
X<>L
FRC
STO 00

Essentially FRC ( (Seed + PI) ^ 3 ) = new seed

[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

[Namir]

(11-12-2016 01:34 PM)Gene Wrote:  Namir,

Any chance you could do the same for these two RNGs ?

RCL 00
R-D
FRC
STO 00


and

RCL 00
PI
+
X^2
ST*L
X<>L
FRC
STO 00

Essentially FRC ( (Seed + PI) ^ 3 ) = new seed

Will do!

Namir