A tutorial on uniform variate generation

ABSTRACT

In typical stochastic simulations, randomness is produced by generating a sequence of independent uniform variates (usually real-valued between 0 and 1, or integer-valued in some interval) and transforming them in the appropriate way. In this tutorial, we examine practical ways of generating such variates on a computer. We compare them in terms of ease of implementation, efficiency, flexibility, theoretical support, and statistical robustness. We look in particular at the following classes of generators: linear congruential (in scalar and matrix form), lagged-Fibonacci (including generalized feedback shift register) and combined. We also mention others and give a bibliographic survey of the most recent papers on the subject.

REFERENCES

• 1: Afflerbach, L. (1986). The Sub-Lattice Structure of Linear Congruential Random Number Generators. Manuscripta Math., 55, 455--465.
• 2: Afflerbach, L. and Grothe, H. (1985). Calculation of Minkowski-Reduced Lattice Bases. Computing, 35, 269--276.
• 3: Afflerbach, L. and Grothe, H. (1988). The Lattice Structure of Pseudo-Random Vectors Generated by Matrix Generators. J. of Computational and Applied Math., 23, 127--131.
• 4: Arvillias, A. C. and Maritsas, D. G. (1978). Partitioning the Period of a Class of m-Sequences and Application to Pseudorandom Number Generation. J. of the ACM, 25, 4, 675--686.
• 5: Bratley, P., Fox, B. L. and Schrage, L. E. (1987). A Guide to Simulation, second edition. Springer-Verlag, New York.
• 6: Chor, B. and Goldreich, O. (1988). Unbiased Bits From Sources of Weak Randomness and Probabilistic Communication Complexity. SIAM J. on Computation, 17, 2, 230--261.
• 7: Collings, B. J. (1987). Compound Random Number Generators. J. of the American Statistical Association, 82, 398, 525--527.
• 8: Collings, B. J. and Hembree, G. B. (1986). Initializing Generalized Feedback Shift Register Pseudorandom Number Generators. J. of the ACM, 33, 706--711.
• 9: Devroye, L. (1986). Non-Uniform Random Variate Generation. Springer-Verlag, New York.
• 10: Dieter, U. (1975). How to Calculate Shortest Vectors in a Lattice. Math. of Computation, 29, 131, 827--833.
• 11: Dudewicz, E. J. and Ralley, T. G. (1981). The Handbook of Random Number Generation and Testing with TESTRAND Computer Code. American Sciences Press, Columbus, Ohio.
• 12: Eichenauer, J. and Lehn, J. (1986). A Nonlinear Congruential Pseudorandom Number Generator. Statistische Hefte, 27, 315--326.
• 13: Eichenauer, J. and Lehn, J. (1987). On the Structure of Quadratic Congruential Sequences. Manuscripta Math., 58, 129--140.
• 14: Eichenauer, J., Lehn, J. and Topuzoglu, A. (1988). A Nonlinear Congruential Pseudorandom Number Generator with Power of Two Modulus. Math. of Computation, 51, 184, 757--759.
• 15: Eichenauer, J., Grothe, H., Lehn, J. and Topuzoglu, A. (1987). A Multiple Recursive Nonlinear Congruential Pseudorandom Number Generator. Manuscripta Math., 59, 331--346.
• 16: Eichenauer, J. and Niederreiter, H. (1988). On Marsaglia's Lattice Test for Pseudorandom Numbers. Manuscripta Math., 62, 245--248.
• 17: Eichenauer-Herrmann, J., Grothe, H. and Lehn, J. (1989). On the Period Length of Pseudorandom Vector Sequences Generated by Matrix Generators. Math. of Computation, 52, 185, 145--148.
• 18: Fishman, G. S. and Moore III, L. S. (1986). An Exhaustive Analysis of Multiplicative Congruential Random Number Generators with Modulus 2³¹ - 1. SIAM J. on Scientific and Statistical Computing 7, 1, 24--45.
• 19: Fushimi, M. (1988). Designing a Uniform Random Number Generator Whose Subsequences Are k-Distributed. SIAM J. on Computing, 17, 1, 89--99.
• 20: Fushimi, M. and Tezuka, S. (1983). The k-Distribution of Generalized Feedback Shift Register Pseudorandom Numbers. Communications of the ACM, 26, 7, 516--523.
• 21: Goldreich, O., Goldwasser, S. and Micali, S. (1986). How to Construct Random Functions. J. of the ACM, 33, 4, 792--807.
• 22: Grothe, H. (1987). Matrix Generators for Pseudo-Random Vectors Generation. Statist. Hefte, 28, 233--238.
• 23: Grothe, H. (1988). Matrixgeneratoren zur Erzeugung gleichverteilter Pseudozufallsvektoren (in german). Dissertation (thesis), Tech. Hochschule Darmstadt, Germany.
• 24: Grube, A. (1973). Mehrfach rekursiv-erzeugte Pseudo-Zufallszahlen (in german). Zeitschrift für angewandte Math. und Mechanik 53, T223-T225.
• 25: Haas, A. (1987). The Multiple Prime Random Number Generator. ACM Trans. on Math. Software, 13, 4, 368--381.
• 26: Kannan, R., Lenstra, A. K. and Lovász, L. (1988). Polynomial Factorization and Nonrandomness of Bits of Algebraic and Some Transcendental Numbers. Math. of Computation, 50, 181, 235--250.
• 27: Knuth, D. E. (1981). The Art of Computer Programming : Seminumerical Algorithms, vol. 2, second edition. Addison-Wesley.
• 28: Law, A. M. and Kelton, W. D. (1982). Simulation Modeling and Analysis, McGraw-Hill.
• 29: L'Ecuyer, P. (1987). A Portable Random Number Generator for 16-Bit Computers. Modeling and Simulation on Microcomputers 1987. The Society for Computer Simulation, 45--49.
• 30: L'Ecuyer, P. (1988). Efficient and Portable Combined Random Number Generators. Communications of the ACM, 31, 6, 742--749 and 774.
• 31: L'Ecuyer, P. and Blouin, F. (1988a). Linear Congruential Generators of Order k > 1. Proceedings of the 1988 Winter Simulation Conference, 432--439.
• 32: L'Ecuyer, P. and Blouin, F. (1988b). Generalized Linear Congruential Generators. Report no. DIUL-RR-8814, Computer Science Dept., Laval University. (Also presented at ORSA/TIMS St-Louis, 1987).
• 33: L'Ecuyer, P. and Côté, S. (1987). A Random Number Package with Splitting Facilities. Report no. DIUL-RR-8705, dépt. d'informatique, Univ. Laval (submitted to ACM Trans. on Math. Software).
• 34: L'Ecuyer, P. and Proulx, R. (1989). About Polynomial Time "Unpredictable" Generators. In these Proceedings.
• 35: Lewis, T. G. and Payne, W. H. (1973). Generalized Feedback Shift Register Pseudorandom Number Algorithm. J. of the ACM, 20, 3, 456--468.
• 36: Lidl, R. and Niederreiter, H. (1986). Introduction to Finite Fields and Their Applications. Cambridge University Press, Cambridge.
• 37: Marsaglia, G. (1968). Random Numbers Fall Mainly in the Planes. Proceedings of the National Academy of Sciences of the United States of America 60, 25--28.
• 38: Marsaglia, G. (1985). A Current View of Random Number Generation. Computer Science and Statistics, Proceedings of the Sixteenth Symposium on the Interface, Atlanta, march 1984. Elsevier Science Publ. (North-Holland), 1985, 3--10.
• 39: Marsaglia, G. and Tsay, L.-H. (1985). Matrices and the Structure of Random Number Sequences. Linear Algebra and its Applications, 67, 147--156.
• 40: Marse, K. and Roberts, S. D. (1983). Implementing a Portable FORTRAN Uniform (0,1) Generator. Simulation, 41, 4, 135--139.
• 41: Modianos, D. T., Scott, R. C. and Cornwell, L. W. (1987). Testing Intrinsic Random Number Generators. Byte, 12, 1, 175--178.
• 42: Monahan, J. F. (1985). Accuracy in Random Number Generation. Math. of Computation, 45, 172, 559--568.
• 43: Morain, F. (1988). Implementation of the Atkin-Gold-wasser-Kilian Primality Testing Algorithm. Rapport de recherche no. 911, INRIA, Rocquencourt, France.
• 44: Mullen, G. L. and Niederreiter, H. (1987). Optimal Characteristic Polynomials for Digital Multistep Pseudorandom Numbers. Computing, 39, 155--163.
• 45: Nance, R. E. and Overstreet, C., Jr. (1978). Some Experimental Observations on the Behavior of Composite Random Number Generators. Operations Research, 26, 5, 915--935.
• 46: Narkiewicz, W. (1984). Uniform Distribution of Sequences of Integers in Residue Classes. Lecture Notes in Mathematics, No. 1087, Springer-Verlag.
• 47: Niederreiter, H. (1978). Quasi-Monte Carlo Methods and Pseudorandom Numbers. Bull. Amer. Math. Soc., 84, 6, 957--1041.
• 48: Niederreiter, H. (1986). A Pseudorandom Vector Generator Based on Finite Field Arithmetic. Math. Japonica, 31, 5, 759--774.
• 49: Niederreiter, H. (1987). A Statistical Analysis of Generalized Feedback Shift Register Pseudorandom Number Generators. SIAM J. Sci. Stat. Comput., 8, 6, 1035--1051.
• 50: Niederreiter, H. (1988). The Serial Test for Digital k-Step Pseudorandom Numbers. Mathematical Journal of Okayama University, 30, 93--119.
• 51: Niederreiter, H. (1989). The Serial Test for Congruential Pseudorandom Numbers Generated by Inversions. Math. of Computation, 52, 185, 135--144.
• 52: Park, S. K. and Miller, K. W. (1988). Random Number Generators: Good Ones Are Hard to Find. Communications of the ACM, 31, 10, 1192--1201.
• 53: Reif, J. H. and Tygar, J. D. (1988). Efficient Parallel Pseudorandom Number Generation. SIAM J. Computing, 17, 2, 404--411.
• 54: Ripley, B. D. (1988). Uses and Abuses of Statistical Simulation. Mathematical Programming, 42, 53--68.
• 55: Tausworthe, R. C. (1965). Random Numbers Generated by Linear Recurrence Modulo Two. Math. of Computation, 19, 201--209.
• 56: Tezuka, S. (1987). Walsh-Spectral Test for GFSR Pseudorandom Numbers. Communications of the ACM, 30, 8, 731--735.
• 57: Tezuka, S. (1988). On Optimal GFSR Pseudorandom Number Generators. Math. of Computation, 50, 182, 531--533.
• 58: Wichmann, B. A. and Hill, I. D. (1982). An Efficient and Portable Pseudo-random Number Generator. Applied Statistics, 31, 188--190. See also corrections and remarks in the same journal by Wichmann and Hill (1984), 33, 123; McLeod (1985), 34, 198--200; Zeisel (1986), 35, 89.
• 59: Wichmann, B. A. and Hill, I. D. (1987). Building a Random Number Generator. Byte, 12, 3, 127--128.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.6 SIMULATION AND MODELING

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.1 Numerical Algorithms and Problems
          Subjects: Computations on matrices; Computations on polynomials

  G. Mathematics of Computing
  G.3 PROBABILITY AND STATISTICS
      Subjects: Random number generation

General Terms:
Algorithms, Design, Theory