Programs: 
RANDOMNU and RANDSEQ 

Version: 
2.0, 5 May 2002 

Description: 
These programs use the affine congruential process to generate uniformly distributed 10 digit pseudorandom integers. 

Compatibility: 


Other programs 
Entire books can be (and have been) written on the subject of what is or is not “random,” so anything I could say here would be oversimplified. There is no such thing as a programmatic random number generator.
However, a pseudorandom number generator is both possible and useful. One class of pseudorandom number generators that has stood the test of time as both simple and “good enough” for a great many purposes are the linear congruential generators. These generators are of the form:
X_{n+1} = aX_{n} (mod Y)
for some multiplier a and some modulus Y, where all the quantities are integers. Related to these, and slightly better for most purposes, are the affine congruential generators
X_{n+1} = aX_{n} + b (mod Y)
These generators add a constant each pass through the algorithm. This prevents the generator from getting stuck at 0, and can be used to alternate even and odd numbers, and so forth. Again, all quantities are integers.
There is no “best” choice for a and b, but some choices are better than others. In particular, a and b should both be odd and without common factors, a and Y should have no common factors, and a should be greater than the square root of Y. This program uses the prime numbers 95165747 for a and 198461 for b, and 10^{10} for Y. Thus, every pseudorandom integer generated is up to 10 digits long. These can be scaled to be uniform pseudorandom numbers on the halfopen interval [0,1) by dividing by 10^{10}. From this uniform [0,1) distribution, any other random distribution can be achieved by applying the inverse of the cumulative distribution function.
Because the calculator has only 15 digits of precision — and because the last three of those 15 digits are used by the calculator to determine whether a number is “near” a number the calculator thinks should be handled specially — the calculator’s multiplication operator cannot be used directly to form the product aX_{n}. Instead, a double precision multiply with halves of the multiplier and multiplicand is used, with intermediate results truncated to the bottom digits to ensure the various intermediate results do not exceed a total of 11 digits. This final sum is further truncated to its low order 10 digits.
This process, while slow, generates better pseudorandom numbers than the calculator’s builtin “random number” function.
The program as written generates uniformly distributed integers between 0 (inclusive) and 10^{10} (exclusive). These integers can easily be used to generate pseudorandom numbers from other distributions.
Taking the result of RANDOMNU and dividing it by 10^{10} will yield a pseudorandom real number uniformly distributed between 0 (inclusive) and 1 (exclusive) with ten digits of precision. This can be further mapped into any desired range by multiplying by the length of the range and adding the lowest point of the range. Finally, this may be truncated to any desired precision, such as truncation to integers.
In the case of finding integers between a and b, inclusive, the size of the range applied to the real numbers must be taken to be ba+1 rather than ba. This is as each integer k results from truncating any pseudorandom number in the halfopen interval [k,k+1). Multiplying the [0,1) pseudorandom number by ba would result in a [0,ba) pseudorandom number, and adding a would then result in a [a,b) pseudorandom number. Truncating this to integers would result in a pseudorandom integer between a and b1, inclusive, rather than the desired a to b, inclusive.
Pseudorandom numbers from any other desired distribution may be generated from the [0,1) real uniformly distributed pseudorandom numbers by applying the inverse cumulative distribution function of the distribution required. If y_{i} = F^{1}(x_{i}), the {y_{i}} form a set of pseudorandom numbers taken from the distribution for which F is the cumulative distribution function. In cases where the inverse cumulative distribution function is not known explicitly, but the cumulative distribution function is known, the inverse can be found implicitly by solving F(y_{i}) = x_{i}, where x_{i} is the generated uniformly distributed pseudorandom number between 0 and 1. As F is monotonic, a bisection algorithm can be used; in the case where F is strictly monotonic and differentiable, Newton’s method can be used also.
If you do not understand what all this means, you probably should not attempt to do anything with pseudorandom numbers until you do understand what all this means.
Load the programs RANDOMNU, RANDSEQ, VRPRE, VRSAVFJ, and VRRESFJ.
If you want to use random numbers in a program, you must first ensure the program VRPRE is invoked. Then you must put an initial (“seed”) value in A and call RANDOMNU repeatedly. Each call to RANDOMNU replaces the value in A with the pseudorandom number next in the sequence. You can transform the 10digit uniformly distributed pseudorandom integers as described in Distribution Transformations above.
The program RANDSEQ uses the program RANDOMNU to generate pseudorandom integers between 0 (inclusive) and 10^{10} (exclusive). It prompts for an initial number with the message:
Seed?
Enter an initial number to start the pseudorandom number generator. RANDSEQ generates the next pseudorandom number in the sequence and displays it. When you press EXE, RANDSEQ generates another number and displays it.
The program is available as a text file with .CAT contents, or may be entered as shown below. A semicolon (“;”) marks the beginning of a comment, and is not to be entered into the calculator. Remember that these programs are copyrighted; see the copyright issues page for limitations on redistribution.
Program RANDOMNU (150 bytes);
; Program RANDOMNU ; ; Description: ; Generates the next pseudorandom number in a sequence of affine ; pseudorandom numbers. ; ; Variables: ; A: On entry, the previous entry in the sequence. On exit, the next ; entry in the sequence. ; F: Half of the double precision product and sum ; ; Calling sequence: ; {previous value}>A ; Prog "RANDOMNU" ; B>{next value} ; ; Implicit inputs: ; List 6: the variable save stack. ; Z: the stack pointer for the variable save stack. ; ; Implicit outputs: ; List 6: the variable save stack. ; Z: the stack pointer for the variable save stack. ; ; Side effects: ; None. ; ; Symbols used: ; > is assignment arrow ; EE is EXP key ; / is division operator Prog "VRSAVFJ" Abs Int A>F 65747Int (F/1EE5)+951(F1EE5Int (F/1EE5))>G 1EE5(G1EE5Int (G/1EE5))>G 65747(F1EE5Int (F/1EE5))+G+198461>G G1EE10Int (G/1EE10)>A Prog "VRRESFJ"
Program RANDSEQ (56 bytes):
; Program RANDSEQ ; ; Description: ; Generates a sequence of pseudorandom numbers based on an initial ; seed value. ; ; Variables: ; A: The seed or previous pseudorandom number, passed to RANDOMNU. ; The next pseudorandom number, returned from RANDOMNU. ; ; Calling sequence: ; None; main program ; ; Implicit inputs: ; None. ; ; Implicit outputs: ; List 6: the variable save stack. ; Z: the stack pointer for the variable save stack. ; ; Side effects: ; None. ; ; Symbols used: ; > is assignment arrow ; _ is display triangle Prog "VRPRE" ; Initialize variable save stack "Seed"?>A ; Get seed into A While 1 ; Infinite loop Prog "RANDOMNU" ; Get the next random number A_ ; Show it WhileEnd ; [End of infinite loop]
[ Previous page  Top of page  Next page ]
Copyright © 2001 Brian Hetrick
Page last updated 5 May 2002.