[A plot of successive random numbers (r_i, r_i+1) generated with the linear congruent method.]

Generating Radom Numbers

The linear congruent random number generator (LCG) is a one of the oldest (but not the best) pseudorandom number generators.  The method generates a sequence of integers x_i over the interval [0, m-1] by the recurrence relation

where the modulus m is greater than zero, the multiplier a is less than m, and the increment c is less than m.  All numbers are integers and all arithmetic is integer arithmetic.  The initial value x₀ is known as the seed. 

If we want floating point numbers in the range [0,1), we divide the pseudorandom integers x_i by m.

Remember to cast  to x_i to a floating point number before doing the division when implementing this algorithm on a computer.

Homework Exercises:

1. Determine the period of the LCG for a=57, c=1, m-256, and seed=10.  Does the period depend on the seed?  Explain the observed period.
2. A simple test for uniformity evaluates the kth moment of random number distribution.
          
   If the distribution is uniform then the moment is 1/(k_1).  Modify the model so as to compute the distribution and test the the first three LCG moments with good parameters.
3. The moments computed in part (2) will have some deviation but this deviation should decrease as the number of samples N increases.  Show that the deviation of the moment varies as sqrt(N).
    

Lecture Notes:

• CSC 231 LCG lecture notes by Tim Chartier.

References

• Wikipedia: http://en.wikipedia.org/wiki/Linear_congruential_generator
• Math World: http://mathworld.wolfram.com/RandomNumber.html

Credits:

The Random LCG Model was created by Wolfgang Christian using the Easy Java Simulations (EJS) version 4.1 authoring and modeling tool. 

You can examine and modify a compiled EJS model if you run the model (double click on the model's jar file), right-click within a plot, and select "Open Ejs Model" from the pop-up menu.  You must, of course, have EJS installed on your computer.  Information about Ejs is available at: <http://www.um.es/fem/Ejs/> and in the OSP comPADRE collection <http://www.compadre.org/OSP/>.