Random Number Generation

Pseudorandom Numbers

The process of creating numbers that simulate randomness on a computer is known as pseudorandom number generation. The "pseudo" in pseudo random refers to the fact that if you use a rule to generate a number, it is by definition not random, though it may appear so, and be close enough to random for all practical purposes.

A truly random process might be rolling a die, drawing a card from a shuffled deck, or picking numbers out of a hat. This method is somewhat inconvenient for a computer.

Most computational methods of generating a distribution of numbers that appears random use a process by which you apply a rule to one number to get another number, and then use that number to generate the next. The first number used is called the "seed" number. If you always start with the same seed, and always use the same rule, you always get the same random numbers. Some computer programs will use a system that stores the last number created even after the computer is restarted. Other computer programs will pick as the first seed something truly random, such as date expressed as the number of milliseconds since the beginning of the year.

The Linear Congruential Generator

A common algorithm for the creation of pseudorandom numbers is the Linear Congruential Generator. Basically, you start with 4 numbers. seed (y0) modulus (m) scale (a) shift (b) You multiply your seed by your scale, then shift, then take the modulus of the shifted number. The result is a number between 0 and m-1. That number replaces your seed, and is used as the seed for the next random number to be generated. In Java, the formula would look like this: randomNumber = (y0*a + b) % m; y0 = randomNumber;

Here is an applet that allow you to see what happens with these types of random number generators. Some values of m and a lead to good random generators, and some do not. A typical way of finding patterns is to take successive calls to the generator to create x-y pairs. The LCG applet plots 1000 points in the range x=[0..1000], y=[0..1000]. Do all values of A, B, and M give you a good random number generator?