On the lattice structure of certain linear congruential sequences related to AWC/SWB generators
HTML articles powered by AMS MathViewer
- by Raymond Couture and Pierre L’Ecuyer PDF
- Math. Comp. 62 (1994), 799-808 Request permission
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
-
J. W. S. Cassels, An introduction to the geometry of numbers, Springer-Verlag, Berlin, 1959.
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.
- 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, DOI 10.1090/S0025-5718-1985-0777278-8
- George S. Fishman and Louis R. Moore III, An exhaustive analysis of multiplicative congruential random number generators with modulus $2^{31}-1$, SIAM J. Sci. Statist. Comput. 7 (1986), no. 1, 24–45. MR 819455, DOI 10.1137/0907002
- F. James, A review of pseudorandom number generators, Comput. Phys. Comm. 60 (1990), no. 3, 329–344. MR 1076267, DOI 10.1016/0010-4655(90)90032-V
- Donald E. Knuth, The art of computer programming. Vol. 2, 2nd ed., Addison-Wesley Series in Computer Science and Information Processing, Addison-Wesley Publishing Co., Reading, Mass., 1981. Seminumerical algorithms. MR 633878 P. L’Ecuyer, Testing random number generators, Proc. 1992 Winter Simulation Conference, IEEE Press, Piscataway, NJ, pp. 305-313.
- 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, DOI 10.1090/S0025-5718-1991-1094954-3
- George Marsaglia, B. Narasimhan, and Arif Zaman, A random number generator for PCs, Comput. Phys. Comm. 60 (1990), no. 3, 345–349. MR 1076268, DOI 10.1016/0010-4655(90)90033-W
- George Marsaglia and Arif Zaman, A new class of random number generators, Ann. Appl. Probab. 1 (1991), no. 3, 462–480. MR 1111529 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).
Additional Information
- © Copyright 1994 American Mathematical Society
- Journal: Math. Comp. 62 (1994), 799-808
- MSC: Primary 65C10
- DOI: https://doi.org/10.1090/S0025-5718-1994-1220826-X
- MathSciNet review: 1220826