Distribution properties of multiply-with-c arry random number generators
HTML articles powered by AMS MathViewer
- by Raymond Couture and Pierre L’Ecuyer PDF
- Math. Comp. 66 (1997), 591-607 Request permission
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 $d$-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
-
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
E. Hecke, Lectures on the theory of algebraic numbers, Springer-Verlag, New York, 1981. MR 83m:12001
D. E. Knuth, The art of computer programming, volume 2: Seminumerical algorithms, second ed., Addison-Wesley, Reading, Mass., 1981. MR 83i:68003
P. L’Ecuyer, Uniform random number generation, Annals of Operations Research 53 (1994), 77-120. MR 95k:65007
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.
G. Marsaglia, Yet another rng, Posted to the electronic billboard sci.stat.math, August 1, 1994.
G. Marsaglia and A. Zaman, A new class of random number generators, The Annals of Applied Probability 1 (1991), 462-480. MR 92h:65009
W. Narkiewicz, Elementary and analytic theory of algebraic numbers, PWN-Polish Scientific Publishers, Warsaw, 1974. MR 50:268
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
C. L. Siegel, Über die Classenzahl quadratischer Zahlkörper, Acta Arithmetica 1 (1935), 83-86.
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.
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): 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 [G. Marsaglia, Yet another rng, Posted to the electronic billboard sci.stat.math, August 1, 1994.] to our attention.
- © Copyright 1997 American Mathematical Society
- Journal: Math. Comp. 66 (1997), 591-607
- MSC (1991): Primary 65C10
- DOI: https://doi.org/10.1090/S0025-5718-97-00827-2
- MathSciNet review: 1401939