Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)



Structural properties for two classes of combined random number generators

Authors: Pierre L’Ecuyer and Shu Tezuka
Journal: Math. Comp. 57 (1991), 735-746
MSC: Primary 65C10
MathSciNet review: 1094954
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: We analyze a class of combined random number generators recently proposed by L’Ecuyer, which combines a set of linear congruential generators (LCG’s) with distinct prime moduli. We show that the geometrical behavior of the vectors of points produced by the combined generator can be approximated by the lattice structure of an associated LCG, whose modulus is the product of the moduli of the individual components. The approximation is good if these individual moduli are near each other and if the dimension of the vectors is large enough. The associated LCG is also exactly equivalent to a slightly different combined generator of the form suggested by Wichmann and Hill. We give illustrations, for which we examine the approximation error and assess the quality of the lattice structure of the associated LCG.

References [Enhancements On Off] (What's this?)

  • L. Afflerbach and H. Grothe, Calculation of Minkowski-reduced lattice bases, Computing 35 (1985), no. 3-4, 269–276 (English, with German summary). MR 825115, DOI
  • U. Dieter, How to calculate shortest vectors in a lattice, Math. Comp. 29 (1975), 827–833. MR 379386, DOI
  • H. Grothe, Matrixgeneratoren zur Erzeugung gleichverteilter Pseudozufallsvektoren, Dissertation, Tech. Hochschule Darmstadt, Germany, 1988.
  • Donald E. Knuth, The art of computer programming. Vol. 2, 2nd ed., Addison-Wesley Publishing Co., Reading, Mass., 1981. Seminumerical algorithms; Addison-Wesley Series in Computer Science and Information Processing. MR 633878
  • Pierre L’Ecuyer, Efficient and portable combined random number generators, Comm. ACM 31 (1988), no. 6, 742–749, 774. MR 945034, DOI
  • ---, Random numbers for simulation, Comm. ACM 33, 10 (1990), 85-97. P. L’Ecuyer and F. Blouin, Multiple recursive and matrix linear congruential generators (submitted).
  • Rudolf Lidl and Harald Niederreiter, Introduction to finite fields and their applications, Cambridge University Press, Cambridge, 1986. MR 860948
  • S. Tezuka, Analysis of L’Ecuyer’s combined random number generator, Technical report RT-5014, IBM Research, Tokyo Research Laboratory, 1989. S. Tezuka and P. L’Ecuyer, Efficient and portable combined Tausworthe random number generators (submitted). B. A. Wichmann and I. D. Hill, An efficient and portable pseudo-random number generator, Applied Statistics 31 (1982), 188-190. (See also corrections and remarks in the same journal by Wichmann and Hill 33 (1984), 123; McLeod 34 (1985), 198-200.) H. Zeisel, A remark on algorithm AS 183, Applied Statistics 35 (1986), 89.

Similar Articles

Retrieve articles in Mathematics of Computation with MSC: 65C10

Retrieve articles in all journals with MSC: 65C10

Additional Information

Keywords: Random number generation, lattice structure, combined generators, Chinese Remainder Theorem
Article copyright: © Copyright 1991 American Mathematical Society