Information on calculator Random Number Generators from PPC Journal articles

11062016, 08:29 PM
Post: #1




Information on calculator Random Number Generators from PPC Journal articles
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. 

11072016, 07:06 AM
Post: #2




RE: Information on calculator Random Number Generators from PPC Journal articles
(11062016 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.
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 

11072016, 08:06 AM
Post: #3




RE: Information on calculator Random Number Generators from PPC Journal articles
Not relevant to the historic generators but the 34S uses a Tausworthe Generator. Good properties and a period around 2^{88}.
I would have used a Mersenne Twister but RAM was lacking. Pauli 

11072016, 07:33 PM
Post: #4




RE: Information on calculator Random Number Generators from PPC Journal articles
(11072016 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^{88}. That's... adequate. Especially if the result can have at most 10^{16} or 10^{34} different values. #) But since the 34s can be equipped with a crystal: have you ever considered some kind of timerelated random number generator? Could something like this have been realized? Dieter 

11072016, 08:12 PM
Post: #5




RE: Information on calculator Random Number Generators from PPC Journal articles
(11072016 07:33 PM)Dieter Wrote:(11072016 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^{88}. Not sure I got your point  do you say that's overkill? 

11072016, 09:15 PM
Post: #6




RE: Information on calculator Random Number Generators from PPC Journal articles
(11072016 08:12 PM)Otto55 Wrote:(11072016 07:33 PM)Dieter Wrote: That's... adequate. Especially if the result can have at most 10^{16} or 10^{34} different values. 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 

11072016, 10:21 PM
Post: #7




RE: Information on calculator Random Number Generators from PPC Journal articles
(11072016 07:33 PM)Dieter Wrote: But since the 34s can be equipped with a crystal: have you ever considered some kind of timerelated 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 

11072016, 10:35 PM
Post: #8




RE: Information on calculator Random Number Generators from PPC Journal articles
Hi, Gene: (11062016 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, RD, FRAC, STO 00 and it worked great for the stated purpose, calculator games (not statistical analysis, not Monte Carlo algorithms, etc). I sent a miniarticle 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 RD 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. Find All My HPrelated Materials here: Valentin Albillo's HP Collection 

11072016, 11:06 PM
Post: #9




RE: Information on calculator Random Number Generators from PPC Journal articles  
11082016, 07:19 AM
(This post was last modified: 11082016 07:27 AM by Dieter.)
Post: #10




RE: Information on calculator Random Number Generators from PPC Journal articles
(11072016 11:06 PM)Gene Wrote: And here's a link to your RD RNG in PPC Journal V7N6: The text says that the seed must not be pi or an integer multiple thereof. In this case the RD 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 RD, 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 nearzero 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 

11082016, 08:08 AM
Post: #11




RE: Information on calculator Random Number Generators from PPC Journal articles
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 pseudorandom matrix on each machine) Cheers, Werner 

11082016, 07:21 PM
Post: #12




RE: Information on calculator Random Number Generators from PPC Journal articles
(11082016 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... (11082016 08:08 AM)Werner Wrote: Same for 41 vs. 42. And here it's 10 vs. 12 digits. (11082016 08:08 AM)Werner Wrote: (I use it mainly to populate random matrices, and so I'd like to have the same pseudorandom matrix on each machine) Simple solution: round the result to, say, 6 places. In most cases the 10digit calculators (41, 67, 97 etc.) will not return more than 7 or 8 digits anyway. Dieter 

11112016, 06:58 PM
Post: #13




RE: Information on calculator Random Number Generators from PPC Journal articles
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 

11112016, 08:08 PM
Post: #14




RE: Information on calculator Random Number Generators from PPC Journal articles
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.


11112016, 09:02 PM
Post: #15




RE: Information on calculator Random Number Generators from PPC Journal articles
(11112016 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 

11122016, 09:42 AM
(This post was last modified: 11122016 09:43 AM by Pekis.)
Post: #16




RE: Information on calculator Random Number Generators from PPC Journal articles
(11112016 09:02 PM)Dieter Wrote:(11112016 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. 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 

11122016, 10:19 AM
(This post was last modified: 11122016 02:52 PM by Namir.)
Post: #17




RE: Information on calculator Random Number Generators from PPC Journal articles
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 autocorrelations 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 ChiSquare 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 

11122016, 01:34 PM
Post: #18




RE: Information on calculator Random Number Generators from PPC Journal articles
Namir,
Any chance you could do the same for these two RNGs ? RCL 00 RD FRC STO 00 and RCL 00 PI + X^2 ST*L X<>L FRC STO 00 Essentially FRC ( (Seed + PI) ^ 3 ) = new seed 

11122016, 06:53 PM
Post: #19




RE: Information on calculator Random Number Generators from PPC Journal articles
(11122016 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). (11122016 10:19 AM)Namir Wrote: The autocorrelations 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 ChiSquare 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 6digit RNs, which allows a fourdigit value for a. With a different choice of the LCG parameters, especially a lower avalue, 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 ndigit 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 

11122016, 07:00 PM
(This post was last modified: 11132016 07:25 AM by Namir.)
Post: #20




RE: Information on calculator Random Number Generators from PPC Journal articles  
« Next Oldest  Next Newest »

User(s) browsing this thread: 1 Guest(s)