Previous page Next page Navigation bar

Programs

Mathematics Programs

Pseudorandom Number Generator

Summary

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:

Is compatible CFX-9850G

Compatible with CFX-9850G

Is compatible FX-7400G

Compatible with FX-7400G

Other programs
required:

VRPRE, VRSAVFJ, VRRESFJ

Detailed Description

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:

Xn+1 = aXn (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

Xn+1 = aXn + 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 1010 for Y. Thus, every pseudorandom integer generated is up to 10 digits long. These can be scaled to be uniform pseudorandom numbers on the half-open interval [0,1) by dividing by 1010. 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 aXn. 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 built-in “random number” function.

Distribution Transformations

The program as written generates uniformly distributed integers between 0 (inclusive) and 1010 (exclusive). These integers can easily be used to generate pseudorandom numbers from other distributions.

Taking the result of RANDOMNU and dividing it by 1010 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 b-a+1 rather than b-a. This is as each integer k results from truncating any pseudorandom number in the half-open interval [k,k+1). Multiplying the [0,1) pseudorandom number by b-a would result in a [0,b-a) 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 b-1, 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 yi = F-1(xi), the {yi} 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(yi) = xi, where xi 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.

Usage

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 10-digit uniformly distributed pseudorandom integers as described in Distribution Transformations above.

Screen shot of RANDSEQ execution The program RANDSEQ uses the program RANDOMNU to generate pseudorandom integers between 0 (inclusive) and 1010 (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.

Program Source

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(F-1EE5Int (F/1EE5))->G
1EE5(G-1EE5Int (G/1EE5))->G
65747(F-1EE5Int (F/1EE5))+G+198461->G
G-1EE10Int (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 ]

Previous page Top of page Next page Navigation bar

Copyright © 2001 Brian Hetrick
Page last updated 5 May 2002.

Brian’s Casio Calculator Corner

Home

Programs

Index

Linkage Conventions

Mathematics

Index

Factorization

Bisection

Newton’s Method

Complex Zeroes

Best Fraction Approximation

Pseudorandom Numbers

Romberg Integration

First Degree ODE

Rounding

Permutations

Finance

Physics

Utility

Tutorial

Puzzles

Site Information

Your Privacy

Site Map

E-mail

Site Technical Data