|
Distribution Properties of Multiply-with-Carry Random Number Generators
Author(s):
Raymond
Couture;
Pierre
L'Ecuyer.
Journal:
Math. Comp.
66
(1997),
591-607.
MSC (1991):
Primary 65C10
Retrieve article in:
PDF
This article is available free of charge
Abstract |
References |
Similar articles |
Additional information
Abstract:
We study the multiply-with-carry family of generators proposed by Marsaglia as a generalization of previous add-with-carry families. We define for them an infinite state space and focus our attention on the (finite) subset of recurrent states. This subset will, in turn, split into possibly several subgenerators. We discuss the uniformity of the  -dimensional distribution of the output of these subgenerators over their full period. In order to improve this uniformity for higher dimensions, we propose a method for finding good parameters in terms of the spectral test. Our results are stated in a general context and are applied to a related complementary multiply-with-carry family of generators.
References:
- 1.
- R. Couture and P. L'Ecuyer, On the lattice structure of certain linear congruential sequences related to AWC/SWB generators, Mathematics of Computation 62 (1994), no. 206, 798-808. MR 94g:65007
- 2.
- E. Hecke, Lectures on the theory of algebraic numbers, Springer-Verlag, New York, 1981. MR 83m:12001
- 3.
- D. E. Knuth, The art of computer programming, volume 2: Seminumerical algorithms, second ed., Addison-Wesley, Reading, Mass., 1981. MR 83i:68003
- 4.
- P. L'Ecuyer, Uniform random number generation, Annals of Operations Research 53 (1994), 77-120. MR 95k:65007
- 5.
- P. L'Ecuyer and R. Couture, An implementation of the lattice and spectral tests for multiple recursive linear random number generators, Informes Journal on Computing, to appear, 1997.
- 6.
- G. Marsaglia, Yet another rng, Posted to the electronic billboard sci.stat.math, August 1, 1994.
- 7.
- G. Marsaglia and A. Zaman, A new class of random number generators, The Annals of Applied Probability 1 (1991), 462-480. MR 92h:65009
- 8.
- W. Narkiewicz, Elementary and analytic theory of algebraic numbers, PWN-Polish Scientific Publishers, Warsaw, 1974. MR 50:268
- 9.
- H. Niederreiter, Random number generation and quasi-Monte Carlo methods, SIAM CBMS-NSF Regional Conference Series in Applied Mathematics, vol. 63, SIAM, Philadelphia, 1992. MR 93h:65008
- 10.
- C. L. Siegel, Über die Classenzahl quadratischer Zahlkörper, Acta Arithmetica 1 (1935), 83-86.
- 11.
- S. Tezuka, P. L'Ecuyer, and R. Couture, On the add-with-carry and subtract-with-borrow random number generators, ACM Transactions of Modeling and Computer Simulation 3 (1994), no. 4, 315-331.
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-97-00827-2
PII:
S 0025-5718(97)00827-2
Keywords:
Random number generation,
recurrences with carry,
lattice structure
Received by editor(s):
November 29, 1995
Received by editor(s) in revised form:
April 24, 1996
Additional Notes:
This work has been supported by NSERC-Canada grant # OGP0110050 and FCAR-Québec grant # 93ER1654 to the second author. We wish to thank Brian Whitney who brought reference [6] to our attention.
Copyright of article:
Copyright
1997,
American Mathematical Society
|
Comments: webmaster@ams.org