Good news for PPC Random-Number Generator

[Namir]

Hi All,

I was reading in the PPC ROM manual and found the label RN that generates random numbers. The PPC ROM manual documents the algorithm used to generate random numbers. I happen to find a random-number testing function in Matalb. I wrote a Matlab function that implements the PPC RN routine and ran a test by generating 1 million random numbers. The PPC RN passed the randomness test with flying colors!!

:-)

Namir

[Gene]

New Seed = Fractional part ( Previous Seed x 9821 + 0.211327 )

Where seed is a decimal number.

This is also the random number generator we put into the 67 FUN rom.

Gene

[Namir]

(05-17-2021 09:01 PM)Gene Wrote:  New Seed = Fractional part ( Previous Seed x 9821 + 0.211327 )

Where seed is a decimal number.

This is also the random number generator we put into the 67 FUN rom.

Gene

Yep, that's the one!!

Namir

[Dave Britten]

Out of curiosity, how does the good old 997 PRNG hold up in the same Matlab test?

[Sylvain Cote]

(05-17-2021 09:01 PM)Gene Wrote:  New Seed = Fractional part ( Previous Seed x 9821 + 0.211327 )

Same number generator used in the HP-41 GAMES PAC (LBL "RNDM")

[Craig Bladow]

Namir,

Matlab uses double precision floating point by default, does the algorithm still pass if limited to single precision or HP-41 precision?

[Albert Chan]

(05-17-2021 11:03 PM)Craig Bladow Wrote:  Matlab uses double precision floating point by default, does the algorithm still pass if limited to single precision or HP-41 precision?

Algorithm is really LCG, disguised as floating points.

Example, we can rewrite it this way (initial seed in units of millionth)

Code:

function make_rnd(seed)
    return function()
        seed = (seed*9821 + 211327) % 1000000
        return seed / 1000000
    end
end

lua> rnd = make_rnd(123456) -- seed 0.123456
lua> rnd(), rnd(), rnd(), rnd(), rnd()
0.672703       0.82749       0.990617       0.060884       0.153091

Seed calculations are integer based, without rounding errors.

[Valentin Albillo]

.
That simple algorithm produces exactly one million pseudo-random integers from 0 to 999999 (or from 0.000000 to 0.999999). After that, it simply repeats the same sequence, which is fine for games and such. I used it to generate 1,000,000 user-selectable random palettes for my Fractval program.

On the other hand, the HP-71B RND function provides a trillion rng's before repeating and passes the Spectral test, which is adequate for serious purposes. Just a one-million period is too few for that, the longer the period the better.

V.

[Namir]

(05-17-2021 10:56 PM)Dave Britten Wrote:  Out of curiosity, how does the good old 997 PRNG hold up in the same Matlab test?

It passes the test for randomness (based on 1 million random numbers)!

Namir

[Namir]

(05-17-2021 11:03 PM)Craig Bladow Wrote:  Namir,

Matlab uses double precision floating point by default, does the algorithm still pass if limited to single precision or HP-41 precision?

I don't know. But let me ask which HP-41C application will need to generate more than a million random number?

Namir

[Massimo Gnerucci]

(05-17-2021 11:03 PM)Sylvain Cote Wrote:  

(05-17-2021 09:01 PM)Gene Wrote:  New Seed = Fractional part ( Previous Seed x 9821 + 0.211327 )

Same number generator used in the HP-41 GAMES PAC (LBL "RNDM")

Yep! That's an old friend.

[Namir]

I also tested the following algorithms that were mentioned in HP documentations:

f = frac((pi+ r)^3) ---> failed randomness test

f = frac((pi+ r)^5) ---> passed randomness test

Namir

[Craig Bladow]

(05-18-2021 03:15 AM)Namir Wrote:  

(05-17-2021 11:03 PM)Craig Bladow Wrote:  Namir,

Matlab uses double precision floating point by default, does the algorithm still pass if limited to single precision or HP-41 precision?

I don't know. But let me ask which HP-41C application will need to generate more than a million random number?

Namir

The application that tests if there are 1,000,000 unique numbers from this algorithm?

[Valentin Albillo]

(05-18-2021 03:15 AM)Namir Wrote:  But let me ask which HP-41C application will need to generate more than a million random number?

This 98-step RPN program generates and uses half a million random numbers in the included worked example and would obtain greater accuracy if using several million, matter of fact I ran it using 100 million random values.

It wouldn't obtain such accuracy if using a generator with shorter period, the results would be unacceptably biased and thus useless.

V.

[Namir]

(05-19-2021 01:48 AM)Craig Bladow Wrote:  

(05-18-2021 03:15 AM)Namir Wrote:  I don't know. But let me ask which HP-41C application will need to generate more than a million random number?

Namir

The application that tests if there are 1,000,000 unique numbers from this algorithm?

In Matlab I sorted the million random numberand checked each number with the next 1000 numbers. There were no matches!

[Craig Bladow]

(05-19-2021 03:29 AM)Namir Wrote:  

(05-19-2021 01:48 AM)Craig Bladow Wrote:  The application that tests if there are 1,000,000 unique numbers from this algorithm?

In Matlab I sorted the million random numberand checked each number with the next 1000 numbers. There were no matches!

I ran it on a DM41X in FAST mode, plugged into USB power, and after many hours it let me know there was a repeat of the initial seed after 1,000,000 unique numbers.

[Thomas Okken]

(05-17-2021 09:01 PM)Gene Wrote:  New Seed = Fractional part ( Previous Seed x 9821 + 0.211327 )

Where seed is a decimal number.

This is also the random number generator we put into the 67 FUN rom.

Not to mention the HP-41C Standard Applications book. I'd think this would be the best-known PRNG among HP-41 veterans.

Page 24:

Quote:Another interesting portion of this program is the random number generator:

r_n+1 = FRC (9821 x r_n + .211327)

This generator was developed by Don Malm as pan of an HP-65 Users' Library program. It passes the spectral test (Knuth, V.2 , § 3.4) and, because its parameters satisfy Theorem A (op . cit., p. 15), it generates one million distinct random numbers between 0 and 1 regardless of th e value selected for r₀. Because the basic random number generator delivers numbers between 0 and 1, it is necessary to do further manipulation of the random numbers to get the integers required for the arithmetic problems. By multiplying the random numbers by an integer N, then taking the integer part, numbers from 0 to N-1 may be generated. This program uses your maximum desired number plus 1 to generate numbers from 0 to your desired maximum.

[Valentin Albillo]

(05-19-2021 01:20 PM)Craig Bladow Wrote:  

(05-19-2021 03:29 AM)Namir Wrote:  In Matlab I sorted the million random numberand checked each number with the next 1000 numbers. There were no matches!

I ran it on a DM41X in FAST mode, plugged into USB power, and after many hours it let me know there was a repeat of the initial seed after 1,000,000 unique numbers.

Try it in Free42, it will run orders of magnitude faster. Free42, though a simulator with far greater accuracy, exactly mimics the HP-71B 12-digit RND results, I tried both RAN vs RND sequences for 100 mllion random numbers and they matched perfectly.

V.

[rprosperi]

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?

Not prodding here, I really don't know.

[Valentin Albillo]

(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".

Best regards.
V.