Good news for PPC Random-Number Generator
05-17-2021, 07:51 PM
Post: #1
 Namir Senior Member Posts: 823 Joined: Dec 2013
Good news for PPC Random-Number Generator
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
05-17-2021, 09:01 PM (This post was last modified: 05-17-2021 09:02 PM by Gene.)
Post: #2
 Gene Moderator Posts: 1,263 Joined: Dec 2013
RE: Good news for PPC Random-Number Generator
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
05-17-2021, 09:19 PM
Post: #3
 Namir Senior Member Posts: 823 Joined: Dec 2013
RE: Good news for PPC Random-Number Generator
(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
05-17-2021, 10:56 PM
Post: #4
 Dave Britten Senior Member Posts: 2,082 Joined: Dec 2013
RE: Good news for PPC Random-Number Generator
Out of curiosity, how does the good old 997 PRNG hold up in the same Matlab test?
05-17-2021, 11:03 PM
Post: #5
 Sylvain Cote Senior Member Posts: 1,784 Joined: Dec 2013
RE: Good news for PPC Random-Number Generator
(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")
05-17-2021, 11:03 PM
Post: #6
 Craig Bladow Senior Member Posts: 335 Joined: Apr 2016
RE: Good news for PPC Random-Number Generator
Namir,

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

CC41 coming soon!
05-17-2021, 11:35 PM
Post: #7
 Albert Chan Senior Member Posts: 1,896 Joined: Jul 2018
RE: Good news for PPC Random-Number Generator
(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.
05-17-2021, 11:50 PM (This post was last modified: 05-18-2021 01:02 AM by Valentin Albillo.)
Post: #8
 Valentin Albillo Senior Member Posts: 815 Joined: Feb 2015
RE: Good news for PPC Random-Number Generator
.
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.

All My Articles & other Materials here:  Valentin Albillo's HP Collection

05-18-2021, 03:13 AM
Post: #9
 Namir Senior Member Posts: 823 Joined: Dec 2013
RE: Good news for PPC Random-Number Generator
(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
05-18-2021, 03:15 AM (This post was last modified: 05-18-2021 03:16 AM by Namir.)
Post: #10
 Namir Senior Member Posts: 823 Joined: Dec 2013
RE: Good news for PPC Random-Number Generator
(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
05-18-2021, 06:02 AM
Post: #11
 Massimo Gnerucci Senior Member Posts: 2,459 Joined: Dec 2013
RE: Good news for PPC Random-Number Generator
(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.

Greetings,
Massimo

-+×÷ ↔ left is right and right is wrong
05-18-2021, 10:35 AM
Post: #12
 Namir Senior Member Posts: 823 Joined: Dec 2013
RE: Good news for PPC Random-Number Generator
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
05-19-2021, 01:48 AM
Post: #13
 Craig Bladow Senior Member Posts: 335 Joined: Apr 2016
RE: Good news for PPC Random-Number Generator
(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?

CC41 coming soon!
05-19-2021, 02:18 AM
Post: #14
 Valentin Albillo Senior Member Posts: 815 Joined: Feb 2015
RE: Good news for PPC Random-Number Generator
(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.

All My Articles & other Materials here:  Valentin Albillo's HP Collection

05-19-2021, 03:29 AM (This post was last modified: 05-19-2021 03:35 AM by Namir.)
Post: #15
 Namir Senior Member Posts: 823 Joined: Dec 2013
RE: Good news for PPC Random-Number Generator
(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!
05-19-2021, 01:20 PM
Post: #16
 Craig Bladow Senior Member Posts: 335 Joined: Apr 2016
RE: Good news for PPC Random-Number Generator
(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.

CC41 coming soon!
05-19-2021, 03:18 PM
Post: #17
 Thomas Okken Senior Member Posts: 1,767 Joined: Feb 2014
RE: Good news for PPC Random-Number Generator
(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:

rn+1 = FRC (9821 x rn + .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 r0. 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.
05-19-2021, 03:23 PM
Post: #18
 Valentin Albillo Senior Member Posts: 815 Joined: Feb 2015
RE: Good news for PPC Random-Number Generator
(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.

All My Articles & other Materials here:  Valentin Albillo's HP Collection

05-19-2021, 05:41 PM
Post: #19
 rprosperi Super Moderator Posts: 5,292 Joined: Dec 2013
RE: Good news for PPC Random-Number Generator
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.

--Bob Prosperi
05-19-2021, 06:31 PM
Post: #20
 Valentin Albillo Senior Member Posts: 815 Joined: Feb 2015
RE: Good news for PPC Random-Number Generator
(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.

All My Articles & other Materials here:  Valentin Albillo's HP Collection

 « Next Oldest | Next Newest »

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