New PRNG algorithms for calculators

[Namir]

In 2002 I took up a project, I called Project 997, to study random number generators for calculators. I started with algorithms that used floating points (limiting the random numbers to 10 digits using MATLAB for the calculations). I based my HHC 2022 presentation for PRNGs based on that work. When I returned home, I added more floating-point-based PRNGs and studied variants of other well-known integer-based PRNGs like Wichmann-Hill, ACORN, and MRG32a. The project required running several laptops daily and for many hours/day and for many weeks.

The approach I used the penalty factor that I had presented at HHC2017 and is a singly number that indicates the goodness of a batch of random numbers. The method I used included three stages:
1) Finding the least penalty factor for a relatively wide range of coefficients. This step determines the values of the optimum coefficients.
2) Finding the least penalty factor for a relatively narrow range of coefficients, based on the best coefficients obtained in step 1.
3)Generate batches of one million random numbers using random seeds and the coefficients obtained in stage 2.

I wrote a seven-part study (plus a summary of best results) and posted on my website. You can click here to access the page that lists all the parts of Project 997.

Enjoy!

Namir

[Eddie W. Shore]

I like how simple the 997 algorithms are, they are a god-sent for calculators that do not have the (psuedo-)random function.

[Namir]

(02-16-2023 02:22 PM)Eddie W. Shore Wrote:  I like how simple the 997 algorithms are, they are a god-sent for calculators that do not have the (pseudo-)random function.

In the last stages of my study I looked at double-random numbers and found two algorithms that out macho-ed the rest of the new algorithms in the entire study!

Namir

[robve]

(02-16-2023 09:03 PM)Namir Wrote:  

(02-16-2023 02:22 PM)Eddie W. Shore Wrote:  I like how simple the 997 algorithms are, they are a god-sent for calculators that do not have the (pseudo-)random function.

Thanks for sharing your in-depth study. Very interesting from a historical perspective!

Note that simple "997" and "983" PRNG algorithms are used in "119 Practical Programs for the TRS-80 Pocket Computer" p.64 Games - Dice Thrower:

20 "R" R=Π+983R
   : R=R-INT R
   : RETURN
and in p.115 Games - "Huh?":

20 L=10L*(L<[E]10)+L*(L>[E]9)
   : R=Π+983R
   : R=R-INT R
   : T=Π+997T
   : T=T-INT T
This is to roll two dice. One dice updates with R=frac(Π+983R) and the other with T=frac(Π+997T).

I didn't see the "983" algorithm results in the links, so perhaps something to add in the future.

- Rob

[robve]

(02-17-2023 08:21 PM)robve Wrote:  Thanks for sharing your in-depth study. Very interesting from a historical perspective!
I didn't see the "983" algorithm results in the links, so perhaps something to add in the future.

In addition, perhaps it should be mentioned whether these PRNG pass the spectral test? And other tests such as the Chi-squared test, as mentioned in an earlier post on how bad some PRNG are (e.g. Sharp PC-1350) when plotting random (x,y) points.

A colleague of mine is an expert on this subject and has written and published about the challenges. Even more challenging is to design Parallel PRNG and quasi-RNG, an important subject in high-performance parallel Monte Carlo simulations.

- Rob

[Namir]

(02-18-2023 01:29 AM)robve Wrote:  

(02-17-2023 08:21 PM)robve Wrote:  Thanks for sharing your in-depth study. Very interesting from a historical perspective!
I didn't see the "983" algorithm results in the links, so perhaps something to add in the future.

In addition, perhaps it should be mentioned whether these PRNG pass the spectral test? And other tests such as the Chi-squared test, as mentioned in an earlier post on how bad some PRNG are (e.g. Sharp PC-1350) when plotting random (x,y) points.

A colleague of mine is an expert on this subject and has written and published about the challenges. Even more challenging is to design Parallel PRNG and quasi-RNG, an important subject in high-performance parallel Monte Carlo simulations.

- Rob

Part 1 lists the Matlab code that calculates the penalty function. This function performs several statistical tests and obtains results (see HHC2017 video). for each test, it compares the absolute difference of theoretic value minus the calculated result. It then multiplies that result by a weight factor. The penalty factor returns the sum of the weighted absolute differences between the theoretical values and the calculated statistics. The small the value, the better is the quality of the random number s generated.

Namir

[Namir]

(02-17-2023 08:21 PM)robve Wrote:  

(02-16-2023 09:03 PM)Namir Wrote:  

Thanks for sharing your in-depth study. Very interesting from a historical perspective!

Note that simple "997" and "983" PRNG algorithms are used in "119 Practical Programs for the TRS-80 Pocket Computer" p.64 Games - Dice Thrower:

20 "R" R=Π+983R
   : R=R-INT R
   : RETURN
and in p.115 Games - "Huh?":

20 L=10L*(L<[E]10)+L*(L>[E]9)
   : R=Π+983R
   : R=R-INT R
   : T=Π+997T
   : T=T-INT T
This is to roll two dice. One dice updates with R=frac(Π+983R) and the other with T=frac(Π+997T).

I didn't see the "983" algorithm results in the links, so perhaps something to add in the future.

- Rob

I chose the integers like 991, 997, etc in an arbitrary "educated guess" fashion. some did very well (especially in the double-random generators (see Part 1) while others did not do well.

I did not check non-HP books since I was aiming at PRNGs for the HP calculators like the HP-765, HP-41C, HP-2s.

Namir