linear congruential sequence

Computer programs can not generate truly random numbers, but they often do generate lists of numbers that "look" random (these lists, or sequences, are called pseudo-random). One of the most common ways to do this is to use a linear congruential sequence. To create such a sequence we first choose four numbers:

m, the modulus (want m > 0);
a, the multiplier (want 0 ≤ a < m);
c, the increment (want 0 ≤ c < m);
X₀, the seed (want 0 ≤ X₀ < m).

Then we define the desired sequence using

X_n+1 = aX_n+c (mod m).

For example, let m=17, a=3, c=11 and X₀=0. Then we get the sequence:

0, 11, 10, 7, 15, 5, 9, 4, 6, 12, 13, 16, 8, 1, 14, 2, 0 (now the sequence repeats).

With m=37, a=24, c=17 and X₀=0, we get the sequence:

0, 17, 18, 5, 26, 12, 9, 11, 22, 27, 36, 30, 34, 19, 29, 10, 35, 6, 13, 33, 32, 8, 24, 1, 4, 2, 28, 23, 14, 20, 16, 31, 21, 3, 15, 7, 0, (now the sequence repeats).

Some computer programs and calculators use a large prime for the modulus to form such a sequence, and then divide each number in the sequence by that prime to return a "random" number between 0 and 1. But we must be careful! With m=37, a=26, c=17 and X₀=0 we get the sequence

0, 17, 15, 0 (now the sequence repeats)

So how do we avoid a short sequence? One way is to choose c relatively prime to m and make sure every prime divisor of m also divides a-1 (and if 4 divides m, that 4 divides a-1); then the sequence has length m. When we let m be a prime and set c to zero, we need to let a be a primitive root modulo p.

Chapter three of Knuth's text (see below) is an extensive and excellent (but highly technical) reference on pseudo-random number generators and how to measure randomness. Let us end with the quote he begins with.

Any one who considers arithmetical methods of producing random digits is, of course, in a state of sin. (John von Neumann, 1951)

References:

Knuth97 (chapter 3)
D. E. Knuth, Seminumerical algorithms, 3rd edition, The Art of Computer Programming Vol, 2, Addison-Wesley, Reading MA, 1997. [This book is an excellent reference for anyone interested in the basic aspects of programming the algorithms mentioned in these pages.]