Multiplicative congruential random number generators with modulus $2^ \beta$: an exhaustive analysis for $\beta =32$ and a partial analysis for $\beta =48$
HTML articles powered by AMS MathViewer
- by George S. Fishman PDF
- Math. Comp. 54 (1990), 331-344 Request permission
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 $\S 2$ 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}}$, $\S 3$ 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}}$, $\S 4$ also presents analogous results for the five best multipliers and for two multipliers suggested in the literature.References
-
J. H. Ahrens and U. Dieter, Uniform random numbers, Technical University of Graz, 1977.
W. Beyer, Private communication, 1988.
- Itshak Borosh and Harald Niederreiter, Optimal multipliers for pseudorandom number generation by the linear congruential method, BIT 23 (1983), no. 1, 65–74. MR 689604, DOI 10.1007/BF01937326 J. W. S. Cassels, An introduction to the geometry of numbers, Springer-Verlag, New York, 1959.
- R. R. Coveyou and R. D. Macpherson, Fourier analysis of uniform random number generators, J. Assoc. Comput. Mach. 14 (1967), 100–119. MR 221727, DOI 10.1145/321371.321379
- U. Dieter, Pseudo-random numbers. The exact distribution of pairs, Math. Comp. 25 (1971), 855–883. MR 298727, DOI 10.1090/S0025-5718-1971-0298727-8
- U. Dieter, How to calculate shortest vectors in a lattice, Math. Comp. 29 (1975), 827–833. MR 379386, DOI 10.1090/S0025-5718-1975-0379386-6 M. Durst, Private communication, 1989.
- 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
- Donald E. Knuth, The art of computer programming, 2nd ed., Addison-Wesley Series in Computer Science and Information Processing, Addison-Wesley Publishing Co., Reading, Mass.-London-Amsterdam, 1975. Volume 1: Fundamental algorithms. MR 0378456
- George Marsaglia, Random numbers fall mainly in the planes, Proc. Nat. Acad. Sci. U.S.A. 61 (1968), 25–28. MR 235695, DOI 10.1073/pnas.61.1.25
- George Marsaglia, The structure of linear congruential sequences, Applications of number theory to numerical analysis (Proc. Sympos., Univ. Montréal, Montreal, Que., 1971) Academic Press, New York, 1972, pp. 249–285. MR 0411115
- Harald Niederreiter, Statistical independence of linear congruential pseudo-random numbers, Bull. Amer. Math. Soc. 82 (1976), no. 6, 927–929. MR 419395, DOI 10.1090/S0002-9904-1976-14222-X
- Harald Niederreiter, Pseudo-random numbers and optimal coefficients, Advances in Math. 26 (1977), no. 2, 99–181. MR 476679, DOI 10.1016/0001-8708(77)90028-7
- Harald Niederreiter, The serial test for linear congruential pseudo-random numbers, Bull. Amer. Math. Soc. 84 (1978), no. 2, 273–274. MR 458791, DOI 10.1090/S0002-9904-1978-14472-3
- Harald Niederreiter, Quasi-Monte Carlo methods and pseudo-random numbers, Bull. Amer. Math. Soc. 84 (1978), no. 6, 957–1041. MR 508447, DOI 10.1090/S0002-9904-1978-14532-7
- Harald Niederreiter, The serial test for pseudorandom numbers generated by the linear congruential method, Numer. Math. 46 (1985), no. 1, 51–68. MR 777824, DOI 10.1007/BF01400255
- C. S. Smith, Multiplicative pseudo-random number generators with prime modulus, J. Assoc. Comput. Mach. 18 (1971), 586–593. MR 295522, DOI 10.1145/321662.321673
Additional Information
- © Copyright 1990 American Mathematical Society
- 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