Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

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

 
 

 

Multiplicative congruential random number generators with modulus $ 2\sp \beta$: an exhaustive analysis for $ \beta=32$ and a partial analysis for $ \beta=48$


Author: George S. Fishman
Journal: Math. Comp. 54 (1990), 331-344
MSC: Primary 65C10; Secondary 11K45
DOI: https://doi.org/10.1090/S0025-5718-1990-0993929-9
MathSciNet review: 993929
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: This paper presents the results of a search to find optimal maximal period multipliers for multiplicative congruential random number generators with moduli $ {2^{32}}$ and $ {2^{48}}$. Here a multiplier is said to be optimal if the distance between adjacent parallel hyperplanes on which k-tuples lie does not exceed the minimal achievable distance by more than 25 percent for $ k = 2, \ldots ,6$. This criterion is considerably more stringent than prevailing standards of acceptability and leads to a total of only 132 multipliers out of the more than 536 million candidate multipliers that exist for modulus $ {2^{32}}$ and to only 42 multipliers in a sample of about 67.1 million tested among the more than $ 351 \times {10^{11}}$ candidate multipliers for modulus $ {2^{48}}$.

Section 1 reviews the basic properties of multiplicative congruential generators and $ \S2$ describes worst case performance measures. These include the maximal distance between adjacent parallel hyperplanes, the minimal number of parallel hyperplanes, the minimal distance between k-tuples and the discrepancy. For modulus $ {2^{32}}$, $ \S3$ presents the ten best multipliers and compares their performances with those of two multipliers that have been recommended in the literature. Comparisons using packing measures in the space of k-tuples and in the dual space are also made. For modulus $ {2^{48}}$, $ \S4$ also presents analogous results for the five best multipliers and for two multipliers suggested in the literature.


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

  • [1] J. H. Ahrens and U. Dieter, Uniform random numbers, Technical University of Graz, 1977.
  • [2] W. Beyer, Private communication, 1988.
  • [3] I. Borosh and H. Niederreiter, Optimal multipliers for pseudo-random number generation by the linear congruential method, BIT 23 (1983), 65-74. MR 689604 (84e:65012)
  • [4] J. W. S. Cassels, An introduction to the geometry of numbers, Springer-Verlag, New York, 1959.
  • [5] R. R. Coveyou and R. D. MacPherson, Fourier analysis of uniform random number generators, J. Assoc. Comput. Mach. 14 (1967), 100-119. MR 0221727 (36:4779)
  • [6] U. Dieter, Pseudo-random numbers: the exact distribution of pairs, Math. Comp. 25 (1971), 855-883. MR 0298727 (45:7776)
  • [7] -, How to calculate shortest vectors in a lattice, Math. Comp. 29 (1975), 827-833. MR 0379386 (52:291)
  • [8] M. Durst, Private communication, 1989.
  • [9] G. S. Fishman and L. R. 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)
  • [10] D. E. Knuth, The art of computer programming: Semi-numerical algorithms, 2nd ed., Addison-Wesley, 1981. MR 0378456 (51:14624)
  • [11] G. Marsaglia, Random numbers fall mainly in the plane, Proc. Nat. Acad. Sci. U.S.A. 61 (1968), 25-28. MR 0235695 (38:3998)
  • [12] -, The structure of linear congruential sequences, in Applications of Number Theory to Numerical Analysis (S. K. Zaremba, ed.), Academic Press, New York, 1972, pp. 249-285. MR 0411115 (53:14854)
  • [13] H. Niederreiter, Statistical independence of linear congruential pseudo-random numbers, Bull. Amer. Math. Soc. 82 (1976), 927-929. MR 0419395 (54:7416)
  • [14] -, Pseudo-random numbers and optimal coefficients, Adv. Math. 26 (1977), 99-181. MR 0476679 (57:16238)
  • [15] -, The serial test for linear congruential pseudo-random numbers, Bull. Amer. Math. Soc. 84 (1978), 273-274. MR 0458791 (56:16991)
  • [16] -, Quasi-Monte Carlo methods and pseudo-random numbers, Bull. Amer. Math. Soc. 84 (1978), 957-1041. MR 508447 (80d:65016)
  • [17] -, The serial test for pseudo-random numbers generated by the linear congruential method, Numer. Math. 46 (1985), 51-68. MR 777824 (86i:65010)
  • [18] C. S. Smith, Multiplicative pseudo-random number generators with prime modulus, J. Assoc. Comput. Mach. 18 (1971), 586-593. MR 0295522 (45:4588)

Similar Articles

Retrieve articles in Mathematics of Computation with MSC: 65C10, 11K45

Retrieve articles in all journals with MSC: 65C10, 11K45


Additional Information

DOI: https://doi.org/10.1090/S0025-5718-1990-0993929-9
Keywords: Congruential generator, discrepancy, random number generation, spectral test
Article copyright: © Copyright 1990 American Mathematical Society

American Mathematical Society