Good news for PPC Random-Number Generator

[Thomas Okken]

(05-19-2021 06:31 PM)Valentin Albillo Wrote:  

(05-19-2021 05:41 PM)rprosperi Wrote:  On these extended test runs to verify generated numbers are not repeated, where are all the generated numbers stored, while verifying subsequent numbers don't match, or are you trusting some algorithm's verification

For this particular algorithm and others like it, if the initial seed ever gets repeated then the whole sequence repeats again so a simple verification requires just to compare each generated number to the initial seed while keeping count of how many numbers are generated. Here, any seed you care to use gets repeated after exactly one millon generated numbers. No need to store anything but the initial seed.

To make sure there are no seeds which result in shorter periods, there are more ellaborated yet still simple algorithms that also don't need storing the whole sequence, see this link, "cycle detection".

With the HP-42S (and RPL, Free42, 71B) RNG, just looking for a repeated number is not sufficient, since they use a 15-digit seed internally, and then truncate it to 12 digits before returning it to the user code environment. The least significant of those 15 digits is always a 1, 3, 7, or 9, so the theoretical maximum cycle is 4e14 long, but I don't know if the actual cycles exhibited by that RNG are that long or whether there are multiple disjoint cycles.

All I know about that RNG comes from this thread: https://groups.google.com/g/comp.sys.hp4...tzMtZhlGoJ

[Albert Chan]

(05-19-2021 10:04 PM)Thomas Okken Wrote:  With the HP-42S (and RPL, Free42, 71B) RNG, just looking for a repeated number is not sufficient, since they use a 15-digit seed internally, and then truncate it to 12 digits before returning it to the user code environment.

Last 3 digits are hidden, but is easily deduced.
Example, I just tried Free42 RAN, and get 0.248998059347, 0.866775882678

>>> a, m = 2851130928467, 10**15
>>> x1, x2 = 248998059347, 866775882678
>>> t = x1 * 1000
>>> [t+b for b in range(1000) if (t+b)*a % m // 1000 == x2]
[248998059347131L]
>>> _[0] * a % m
866775882678177L
>>> _ * a % m
34252568964659L

It predicted next RAN is 0.0342525689646, which is indeed the case.

Quote: The least significant of those 15 digits is always a 1, 3, 7, or 9, so the theoretical maximum cycle is 4e14 long, but I don't know if the actual cycles exhibited by that RNG are that long or whether there are multiple disjoint cycles.

Period is 5E13, from Joe Horn's post

[rprosperi]

Thanks Valentin! An excellent and clear explanation for those of us with somewhat thicker craniums. Like so many other things, it's completely obvious and trivial, once you understand it.

Thanks for the education!