|
Orbits and Lattices for Linear Random Number Generators with Composite Moduli
Author(s):
Raymond
Couture;
Pierre
L'Ecuyer.
Journal:
Math. Comp.
65
(1996),
189-201.
MSC (1991):
Primary 65C10
Retrieve article in:
PDF DVI PostScript
This article is available free of charge
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:
- 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
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
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
DOI:
10.1090/S0025-5718-96-00673-4
PII:
S 0025-5718(96)00673-4
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.
Copyright of article:
Copyright
1996,
American Mathematical Society
|
Comments: webmaster@ams.org