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.

**[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), no. 170, 463–471. MR**777278**, 10.1090/S0025-5718-1985-0777278-8**[4]**George S. Fishman and Louis R. Moore III,*An exhaustive analysis of multiplicative congruential random number generators with modulus 2³¹-1*, SIAM J. Sci. Statist. Comput.**7**(1986), no. 1, 24–45. MR**819455**, 10.1137/0907002**[5]**F. James,*A review of pseudorandom number generators*, Comput. Phys. Comm.**60**(1990), no. 3, 329–344. MR**1076267**, 10.1016/0010-4655(90)90032-V**[6]**Donald E. Knuth,*The art of computer programming. Vol. 2*, 2nd ed., Addison-Wesley Publishing Co., Reading, Mass., 1981. Seminumerical algorithms; Addison-Wesley Series in Computer Science and Information Processing. MR**633878****[7]**P. L'Ecuyer,*Testing random number generators*, Proc. 1992 Winter Simulation Conference, IEEE Press, Piscataway, NJ, pp. 305-313.**[8]**Pierre L’Ecuyer and Shu Tezuka,*Structural properties for two classes of combined random number generators*, Math. Comp.**57**(1991), no. 196, 735–746. MR**1094954**, 10.1090/S0025-5718-1991-1094954-3**[9]**George Marsaglia, B. Narasimhan, and Arif Zaman,*A random number generator for PCs*, Comput. Phys. Comm.**60**(1990), no. 3, 345–349. MR**1076268**, 10.1016/0010-4655(90)90033-W**[10]**George Marsaglia and Arif Zaman,*A new class of random number generators*, Ann. Appl. Probab.**1**(1991), no. 3, 462–480. MR**1111529****[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).

Retrieve articles in *Mathematics of Computation*
with MSC:
65C10

Retrieve articles in all journals with MSC: 65C10

Additional Information

DOI:
https://doi.org/10.1090/S0025-5718-1994-1220826-X

Keywords:
Random number generation,
lattice structure,
combined generators

Article copyright:
© Copyright 1994
American Mathematical Society