Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

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



Orbits and Lattices
for Linear Random Number Generators
with Composite Moduli

Authors: Raymond Couture and Pierre L’Ecuyer
Journal: Math. Comp. 65 (1996), 189-201
MSC (1991): Primary 65C10
MathSciNet review: 1322887
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: In order to analyze certain types of combinations of multiple recursive linear congruential generators (MRGs), we introduce a generalized spectral test. We show how to apply the test in large dimensions by a recursive procedure based on the fact that such combinations are subgenerators of other MRGs with composite moduli. We illustrate this with the well-known RANMAR generator. We also design an algorithm generalizing the procedure to arbitrary random number generators.

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

  • 1 R. Couture and P. L'Ecuyer, On the lattice structure of certain linear congruential sequences related to AWC/SWB generators, Math. Comp. 62 (1994), 798--808. MR 94g:65007
  • 2 U. Fincke and M. Pohst, Improved methods for calculating vectors of short length in a lattice, including a complexity analysis, Math. Comp. 44 (1985) 463--471. MR 86e:11050
  • 3 A. Grube, Mehrfach rekursiv-erzeugte Pseudo-Zufallszahlen, Z. Angew. Math. Mech. 53 (1973), T223--T225. MR 50:3524
  • 4 F. James, A review of pseudorandom number generators, Comput. Phys. Comm. 60 (1990), 329--344. MR 91i:65013
  • 5 D. E. Knuth, The art of computer programming vol. 2, Seminumerical algorithms, 2nd ed., Addison-Wesley, Reading, MA, 1981. MR 83i:68003
  • 6 P. L'Ecuyer, Combined multiple recursive generators, Operations Research, to appear.
  • 7 P. L'Ecuyer, F. Blouin, and R. Couture, A search for good multiple recursive random number generators, ACM Trans. Modeling and Computer Simulation 3 (1993), 87--98.
  • 8 P. L'Ecuyer and R. Couture, An implementation of the lattice and spectral tests for linear congruential and multiple recursive generators, submitted.
  • 9 P. L'Ecuyer and S. Tezuka, Structural properties for two classes of combined random number generators, Math. Comp. 57 (1991), 735--746. MR 92a:65034
  • 10 G. Marsaglia, A. Zaman, and W.-W. Tsang, Toward a universal random number generator, Statist. Probab. Lett. 9 (1990), 35--39. MR 91a:65008
  • 11 H. Niederreiter, Random number generation and quasi-Monte Carlo methods, SIAM CBMS-NSF Regional Conference Series in Appl. Math., vol. 63, SIAM, Philadelphia, PA, 1992. MR 93h:65008
  • 12 B. A. Wichmann and I. D. Hill, An efficient and portable pseudo-random number generator, Appl. Statist. 31 (1982), 188--190.

Similar Articles

Retrieve articles in Mathematics of Computation of the American Mathematical Society with MSC (1991): 65C10

Retrieve articles in all journals with MSC (1991): 65C10

Additional Information

Raymond Couture
Affiliation: Département d’Informatique, et de Recherche Opérationnelle, Université de Montréal, C.P. 6128, Succ. Centre-Ville, Montréal, H3C 3J7, Canada

Pierre L’Ecuyer
Affiliation: Département d’Informatique et de Recherche Opérationnelle, Université de Montréal, C.P. 6128, Succ. Centre-Ville, Montréal, H3C 3J7, Canada

Keywords: Random number generation, lattice structure, combined generators
Received by editor(s): April 6, 1994
Received by editor(s) in revised form: November 29, 1994
Additional Notes: This work has been supported by NSERC-Canada grant # OGP0110050 and FCAR-Québec grant # 93ER1654 to the second author.
Article copyright: © Copyright 1996 American Mathematical Society

American Mathematical Society