Computer Randomness

Any procedure that generally produces a series of numbers that pass a reasonable set of statistical tests as not non-random is called a pseudo-random number generator. This definition depends on `a reasonable set of statistical tests for non-randomness'; this is a weak standard for randomness. It also ignores the unpredictable nature of randomness. This is the definition that has guided the development of computer generated random sequences during the first three decades of computer studies. It is still popular today.

Often the next number in a mechanically generated series can be easily predicted from prior numbers, even though the series may have passed many statistical tests. But for many computer uses like simulation experiments, and for some games, this definition provides enough `unpredictability' to satisfy a user.

For many years, starting in the mid 1950s, soon after the start of computers, the most common computer pseudo-random number generator was based on this computation:

This is a pretty fast algorithm, although multiplication and division are slow machine operations. This generator is sensitive to the choice of the constants c₁ and c₂, and c₃. Usually c₃ is picked to be some power of 2, usually the word size of the machine, so that division doesn't have to be used to implement the mod function; the machine wrap-around does it for you. For many library pseudo-random number generators the value of c₂ is commonly zero, but this leads to a disaster if the prior random is ever zero. Usually the seed (the first pseudo-random number) is supplied by the user; and the two constants, c₁ and c₂, are built into the pseudo-random number generator. Generators of this form are called linear congruential random number generators or LCGs for short.

It only takes two or three numbers from an LCG and a little calculation to be able to predict future numbers. So they don't produce good randoms in the sense of not knowing the future from the past. Although used in a game where you don't see the numbers involved, it is difficult to predict what will happen next; even though the series is highly predictable.

All LCGs eventually repeat. This is called the period of the pseudo-random number generator. Any finite procedure that generates pseudo-random numbers will eventually repeat. One can make the pseudo-random sequence arbitrarily long, but eventually the procedure will run out of energy to produce new number sequences and begin to repeat itself. Thus no finite procedure can be a mathematical random sequence generator.

LCGs were the basis for most of the simulation research in the 1960s and 1970s. But LCGs have many bad properties that may make simulation results inaccurate or even completely wrong. For example if one takes pairs of sequential numbers output from an LCG and plot them one will find they group into diagonal lines on a plane. If you take the sine of the first member of the sequential pair and the cosine of the next member and plot the results you will find all the points lie on single continuous spiral. This is not an accident, it comes from the ordered nature of the linear formula interacting with the modulus. Points falling off the line of the spiral will never occur. If this `structure' of the numbers could affect simulation results then using an LCG is probably misguided. The built-in random number generator in Pascal, C, Fortran, and most other high level languages is an LCG, so beware this problem has not gone away. With some LCGs the low-order bits of the number repeat regularly, and this can cause problems as well. Used as a floating point number this has a minimal effect, used as an integer, however, it could cause `neurotic' program behavior, that you may find hard to understand.

Using mathematically well behaved functions to produce randomness is not ideal, because the predictable behavior of these functions eventually shows through in the resulting sequence. A better approach is to use arbitrary tables as functions or use exclusive-or to combine several pseudo-random sequences into one that is difficult to predict.

Recently several pseudo-random number generators have been designed that do a much better job. These new algorithms have long periods, and the numbers they produce are difficult to predict from prior numbers in the sequence.