Information on calculator Random Number Generators from PPC Journal articles

[ttw]

There are some more or less realiable methods of generating pseuo-random numbers on a calculator. Which particular calculator is used determines the suitable and programming of each method. The suggested ones in the calculator literature are not known to be very good. There are two easy-to implement classes that can be combined if desired, although detailed properties of the combination have not been investigated extensively.

The first is the LGC (Linear Congruential Generator), also called the Lehmer generator. It works on a simple recursive formula.

x(0): the seed
X(n): the nth number
A: the seed
M: the modulus
b: the addend

X(n)=A*X(n-1)+b Modulo M

This can be converted to a fraction between 0 and 1 by forming Y = X(n)/M

There are conditions on the parameters A, M, b, and X(0) to insure that the generator cycles over the numbers from 0 to M-1 or a large fraction thereof.

If M is a power of two, then the conditions are easy. The multiplier, A, must be congruent to either 3 or 5 modulo 8 and b must be odd; x(0) is irrelevent. X(n+1)=A*X(n)+b Modulo M.

Another possibility is to use the recursion X(n+1)=A*X(n) Modulo M with X(0) being odd. This is also sufficient the the period is 1/4 as long.

In general a long period is wanted. There are lots of choices (a few are given below). A really long (like 2^256 or so) generator is pretty good for numerical work but the generator is easily predictable. Note that the last bit cycles with period 2:...01010101...., the next with period 4, etc. The leading bit cycles with length M.

Several sets of parameters:

M = 256, A = 181, b odd (too small for real work, but one can step through it on a calculator to see what happens.

M = 2^32, A = 2891335453, b odd (A chosen by search)

This size has been popular on 32-bit computers for obvious reasons. One probably cannot cycle it on a calculator.

M = 2^64, A = 4976020386757901309, b odd (A chosen by search)

This generator is longer than most simulations are run for. I used it for caluclator games.

The second class of generators is the Shift Register Generator or Tausworthe Generator. It is based on shift a register over 1 bit and then XORing the result with a bit pattern (a primitive polynomial in the finite field the length of the generator to be technical) if the bit shifted out is a 1 bit. These generator generate good bit streams but not as good binary integers. There are lots of fixes. Similar generators are used for some encryption methods as (for example) using one generator to clock another or outputting one generator based on whether the other generator is a 1.

M is the size, P is the primitive polynomial (looked up in a table), T(0) must be non-zero. This genrator has a cycle 2^L-1 for length L; it generates all non-zero integers in range. The recurrence is given below (here, I'm shifting to the right to be easier to program). LSB stands for the Least Significant Bit (the units digit if read as a binary number), RS for right shift by one bit, end off, zero fill. The polynomials are given in hex.

IF LSB(T(n)) = 1
THEN T(n+1) = RS(T(n)) XOR P
ELSE T(n+1) = RS(T(n))
ENDIF

M = 2^8 (an 8 bit generator), P = B8
M = 2^32 (a 32 bit generator), P = 80200003
M = 2^64 (a 64 bit generator), P = D800000000000000

One way to create a longer generator is to combine two (or more) generator with differing lengths. With the proper combiner, the cycle length of the resulting generator is the Least Common Multiple of the cycles of the constituents. I've always used a shift register and a linear congruentialg with the same length (cycle 2^L and 2^L-1 so no thinking). The length L objects can be treated as integers or bit-strings. As bit strings the obvious operation is XOR; as integers, the obvious operations are Add and Subtract (modulo 2^L).