Orbits and lattices for linear random number generators with composite moduli
HTML articles powered by AMS MathViewer
- by Raymond Couture and Pierre L’Ecuyer PDF
- Math. Comp. 65 (1996), 189-201 Request permission
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
- Raymond Couture and Pierre L’Ecuyer, On the lattice structure of certain linear congruential sequences related to AWC/SWB generators, Math. Comp. 62 (1994), no. 206, 799–808. MR 1220826, DOI 10.1090/S0025-5718-1994-1220826-X
- U. Fincke and M. Pohst, Improved methods for calculating vectors of short length in a lattice, including a complexity analysis, Math. Comp. 44 (1985), no. 170, 463–471. MR 777278, DOI 10.1090/S0025-5718-1985-0777278-8
- A. Grube, Mehrfach rekursiv-erzeugte Pseudo-Zufallszahlen, Z. Angew. Math. Mech. 53 (1973), T223–T225 (German). MR 351033
- F. James, A review of pseudorandom number generators, Comput. Phys. Comm. 60 (1990), no. 3, 329–344. MR 1076267, DOI 10.1016/0010-4655(90)90032-V
- Donald E. Knuth, The art of computer programming. Vol. 2, 2nd ed., Addison-Wesley Series in Computer Science and Information Processing, Addison-Wesley Publishing Co., Reading, Mass., 1981. Seminumerical algorithms. MR 633878
- P. L’Ecuyer, Combined multiple recursive generators, Operations Research, to appear.
- 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.
- P. L’Ecuyer and R. Couture, An implementation of the lattice and spectral tests for linear congruential and multiple recursive generators, submitted.
- Pierre L’Ecuyer and Shu Tezuka, Structural properties for two classes of combined random number generators, Math. Comp. 57 (1991), no. 196, 735–746. MR 1094954, DOI 10.1090/S0025-5718-1991-1094954-3
- George Marsaglia, Arif Zaman, and Wai Wan Tsang, Toward a universal random number generator, Statist. Probab. Lett. 9 (1990), no. 1, 35–39. MR 1035988, DOI 10.1016/0167-7152(90)90092-L
- Harald Niederreiter, Random number generation and quasi-Monte Carlo methods, CBMS-NSF Regional Conference Series in Applied Mathematics, vol. 63, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 1992. MR 1172997, DOI 10.1137/1.9781611970081
- B. A. Wichmann and I. D. Hill, An efficient and portable pseudo-random number generator, Appl. Statist. 31 (1982), 188–190.
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
- Email: couture@iro.umontreal.ca
- 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
- Email: lecuyer@iro.umontreal.ca
- 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.
- © Copyright 1996 American Mathematical Society
- Journal: Math. Comp. 65 (1996), 189-201
- MSC (1991): Primary 65C10
- DOI: https://doi.org/10.1090/S0025-5718-96-00673-4
- MathSciNet review: 1322887