HP Prime: The Period of a Pseudo Random Number Generator
Introduction
Most scientific calculators, mathematical programs, and spreadsheet programs will have random number generators that will generate numbers at random. The most common generator is a one that produces numbers between 0 and 1. Additional random functions will also allow the user to generate random integers and random numbers that fit the normal distribution.
It wasn't always this way.
In the 1970s and into the 1980s, scientific calculators and some computers did not have random number functions. This facilitated a need for pseudo random number generators, hereafter noted as PRNG, which date back to the 1940s. PRNGs used recursive functions to generate random numbers between 0 and 1. Several examples include:
x_n+1 = frac(997 * x_n)
x_n+1 = frac(147 * x_n)
x_n+1 = frac( (π + x_n)^5 )
You select a seed, which the RPNG starts generating random numbers. For example, using the PRNG of x_n+1 = frac(147 * x_n) with a seed of π/3 generates the random numbers:
0.938040026
0.891883822
0.106921834
0.717509598
0.473910906
0.664903182
and so on..
HP Prime Program RNGTEST
The program RNGTEST tests the period of a pseudo random number generator, given a seed. The period of a pseudo random number generator at a given seed is how many iterations it takes for the generator to return to it's initial (first) random number. For example, if a generator's first random number is 0.1 and it takes 20 iterations for the generator to reach 0.1 again, then the period is 20.
The program sets an arbitrary maximum limit, set in the code of 50,000. If the count reaches this limit, then the period of the generator is at least this maximum, possibly infinity. You may change this limit as wished. Thankfully the HP Prime's processor is fast, so the calculator can handle many interactions quickly. Older calculators will require more time.
The program:
rngf(x); // random number generator
EXPORT RNGTEST(s)
BEGIN
// s = seed
// 2018-11-04 EWS
LOCAL i,k,x:=s;
// initial point
i:=rngf(x);
k:=0;
PRINT();
// loop
REPEAT
x:=rngf(x);
PRINT(k+" , "+x);
k:=k+1;
UNTIL (x==i AND k>1) OR k>50000;
RETURN k-1;
END;
rngf(x)
BEGIN
RETURN FP(997*x);
END;
Note: In the rngf(x) subroutine, you can insert any pseudo random number generator you want.
Testing a Simple PRNG
I had set up the program to test a simple PRNG x_n+1 = frac(997 * x_n).
If the seed is picked with one decimal point (0.1 through 0.9), the period is only 4. That means, the generator cycles only 4 numbers before repeating again, with the exception is 0.5, which period is only 1. Specifically:
The seed 0.1 generates 0.1, 0.7, 0.9, 0.3, and then repeats.
The seed 0.2 generates 0.2, 0.4, 0.8, 0.6, and then repeats.
The seed 0.3 generates 0.3, 0.1, 0.7, 0.9, and then repeats.
The seed 0.4 generates 0.4, 0.8, 0.6, 0.2 and then repeats.
The seed 0.5 generates 0.5 and only 0.5.
You can see the repeating periods below. (click on the picture below)
For two decimal point seeds 0.01 to 0.99 (leaving out 0.10, 0.20, etc), from an random sample, you either get a period of 20, or if the seed ends in 5, a period of 4.
For three decimal points seeds 0.001 to 0.999 (leaving out 0.100, 0.110, etc), from a random sample, you either get a period of 100, or if the seed ends in 5, a period of 20.
For simple PRNGs, you are going to a seed with many decimal places to be able to generate different random numbers.
Source:
Shammas, Namir "New Pseudo Random Number Generators: Part 1" 2015. http://www.namirshammas.com/NEW/prng1.pdf Retrieved October 28, 2018.
Eddie
Introduction
Most scientific calculators, mathematical programs, and spreadsheet programs will have random number generators that will generate numbers at random. The most common generator is a one that produces numbers between 0 and 1. Additional random functions will also allow the user to generate random integers and random numbers that fit the normal distribution.
It wasn't always this way.
In the 1970s and into the 1980s, scientific calculators and some computers did not have random number functions. This facilitated a need for pseudo random number generators, hereafter noted as PRNG, which date back to the 1940s. PRNGs used recursive functions to generate random numbers between 0 and 1. Several examples include:
x_n+1 = frac(997 * x_n)
x_n+1 = frac(147 * x_n)
x_n+1 = frac( (π + x_n)^5 )
You select a seed, which the RPNG starts generating random numbers. For example, using the PRNG of x_n+1 = frac(147 * x_n) with a seed of π/3 generates the random numbers:
0.938040026
0.891883822
0.106921834
0.717509598
0.473910906
0.664903182
and so on..
HP Prime Program RNGTEST
The program RNGTEST tests the period of a pseudo random number generator, given a seed. The period of a pseudo random number generator at a given seed is how many iterations it takes for the generator to return to it's initial (first) random number. For example, if a generator's first random number is 0.1 and it takes 20 iterations for the generator to reach 0.1 again, then the period is 20.
The program sets an arbitrary maximum limit, set in the code of 50,000. If the count reaches this limit, then the period of the generator is at least this maximum, possibly infinity. You may change this limit as wished. Thankfully the HP Prime's processor is fast, so the calculator can handle many interactions quickly. Older calculators will require more time.
The program:
rngf(x); // random number generator
EXPORT RNGTEST(s)
BEGIN
// s = seed
// 2018-11-04 EWS
LOCAL i,k,x:=s;
// initial point
i:=rngf(x);
k:=0;
PRINT();
// loop
REPEAT
x:=rngf(x);
PRINT(k+" , "+x);
k:=k+1;
UNTIL (x==i AND k>1) OR k>50000;
RETURN k-1;
END;
rngf(x)
BEGIN
RETURN FP(997*x);
END;
Note: In the rngf(x) subroutine, you can insert any pseudo random number generator you want.
Testing a Simple PRNG
I had set up the program to test a simple PRNG x_n+1 = frac(997 * x_n).
If the seed is picked with one decimal point (0.1 through 0.9), the period is only 4. That means, the generator cycles only 4 numbers before repeating again, with the exception is 0.5, which period is only 1. Specifically:
The seed 0.1 generates 0.1, 0.7, 0.9, 0.3, and then repeats.
The seed 0.2 generates 0.2, 0.4, 0.8, 0.6, and then repeats.
The seed 0.3 generates 0.3, 0.1, 0.7, 0.9, and then repeats.
The seed 0.4 generates 0.4, 0.8, 0.6, 0.2 and then repeats.
The seed 0.5 generates 0.5 and only 0.5.
You can see the repeating periods below. (click on the picture below)
For two decimal point seeds 0.01 to 0.99 (leaving out 0.10, 0.20, etc), from an random sample, you either get a period of 20, or if the seed ends in 5, a period of 4.
For three decimal points seeds 0.001 to 0.999 (leaving out 0.100, 0.110, etc), from a random sample, you either get a period of 100, or if the seed ends in 5, a period of 20.
For simple PRNGs, you are going to a seed with many decimal places to be able to generate different random numbers.
Source:
Shammas, Namir "New Pseudo Random Number Generators: Part 1" 2015. http://www.namirshammas.com/NEW/prng1.pdf Retrieved October 28, 2018.
Eddie
All original content copyright, © 2011-2018. Edward Shore. Unauthorized use and/or unauthorized distribution for commercial purposes without express and written permission from the author is strictly prohibited. This blog entry may be distributed for noncommercial purposes, provided that full credit is given to the author. Please contact the author if you have questions.
