Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

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



Distribution Properties of
Multiply-with-Carry Random Number Generators

Authors: Raymond Couture and Pierre L’Ecuyer
Journal: Math. Comp. 66 (1997), 591-607
MSC (1991): Primary 65C10
MathSciNet review: 1401939
Full-text PDF

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 $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 [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, 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 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, 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 \cite{rMAR94a} to our attention.
Article copyright: © Copyright 1997 American Mathematical Society

American Mathematical Society