Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

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



On the lattice structure of certain linear congruential sequences related to AWC/SWB generators

Authors: Raymond Couture and Pierre L’Ecuyer
Journal: Math. Comp. 62 (1994), 799-808
MSC: Primary 65C10
MathSciNet review: 1220826
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: We analyze the lattice structure of certain types of linear congruential generators (LCGs), which include close approximations to the add-with-carry and subtract-with-borrow (AWC/SWB) random number generators introduced by Marsaglia and Zaman, and also to combinations of the latter with ordinary LCGs. It follows from our results that all these generators have an unfavorable lattice structure in large dimensions.

References [Enhancements On Off] (What's this?)

  • [1] J. W. S. Cassels, An introduction to the geometry of numbers, Springer-Verlag, Berlin, 1959.
  • [2] A. M. Ferrenberg, D. P. Landau, and Y. J. Wong, Monte Carlo simulations: hidden errors from "good" random number generators, Phys. Rev. Lett. 69 (1992), 3382-3384.
  • [3] 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 777278 (86e:11050)
  • [4] G. Fishman and L. Moore, An exhaustive analysis of multiplicative congruential random number generators with modulus $ {2^{31}} - 1$, SIAM J. Sci. Statist. Comput. 7 (1986), 24-45. MR 819455 (87g:65010a)
  • [5] F. James, A review of pseudorandom number generators, Comput. Phys. Comm. 60 (1990), 329-344. MR 1076267 (91i:65013)
  • [6] D. E. Knuth, The art of computer programming: Seminumerical algorithms, vol. 2, 2nd ed., Addison-Wesley, Reading, Mass., 1981. MR 633878 (83i:68003)
  • [7] P. L'Ecuyer, Testing random number generators, Proc. 1992 Winter Simulation Conference, IEEE Press, Piscataway, NJ, pp. 305-313.
  • [8] P. L'Ecuyer and S. Tezuka, Structural properties for two classes of combined random number generators, Math. Comp. 57 (1991), 735-746. MR 1094954 (92a:65034)
  • [9] G. Marsaglia, B. Narasimhan, and A. Zaman, A random number generator for PC's, Comput. Phys. Comm. 60 (1990), 345-349. MR 1076268
  • [10] G. Marsaglia and A. Zaman, A new class of random number generators, Ann. Appl. Probab. 1 (1991), 462-480. MR 1111529 (92h:65009)
  • [11] S. Tezuka, P. L'Ecuyer, and R. Couture, On the lattice structure of the add-with-carry and subtract-with-borrow random number generators, ACM Trans. Model. Comput. Sim. (to appear).

Similar Articles

Retrieve articles in Mathematics of Computation with MSC: 65C10

Retrieve articles in all journals with MSC: 65C10

Additional Information

Keywords: Random number generation, lattice structure, combined generators
Article copyright: © Copyright 1994 American Mathematical Society

American Mathematical Society