An Exhaustive Analysis of Multiplicative Congruential Random Number Generators with Modulus $2^{31} - 1$
Authors:
- George S. FishmanGFGeorge S. Fishman
- Iii Louis R. MooreIMIii Louis R. Moore
- 1 January 1986
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Scientific and Statistical Computing
- Vol. 7 (1) , 24-45
Abstract
This paper presents the results of an exhaustive search to find optimal full period multipliers for the multiplicative congruential random number generator with prime modulus $2^{31} - 1$. 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, \cdots ,6$. This criterion is considerably more stringent than prevailing standards of acceptability and leads to a total of only 414 multipliers among the more than 534 million candidate multipliers. Section 1 reviews the basic properties of linear congruential generators and § 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, the lattice ratio and the discrepancy. Section 3 presents the five best multipliers and compares their performances with those of three commonly employed multipliers for all measures but the lattice test. Comparisons using packing measures in the space of k-tuples and in the dual space are also made. Section 4 presents the results of applying a battery of statistical tests to the best five to detect local departures from randomness. None were found. The Appendix contains a list of all optimal multipliers.
Keywords
This publication has 16 references indexed in Scilit:
- Optimal multipliers for pseudo-random number generation by the linear congruential methodBIT Numerical Mathematics, 1983
- How to calculate shortest vectors in a latticeMathematics of Computation, 1975
- The Structure of Linear Congruential Sequences1972
- The lattice structure of multiplicative congruential pseudo-random vectorsMathematics of Computation, 1971
- RANDOM NUMBERS FALL MAINLY IN THE PLANESProceedings of the National Academy of Sciences of the United States of America, 1968
- Fourier Analysis of Uniform Random Number GeneratorsJournal of the ACM, 1967
- An Introduction to the Geometry of Numbers1959
- On Several Statistics Related to Empirical Distribution FunctionsThe Annals of Mathematical Statistics, 1958
- A Test of Goodness of FitJournal of the American Statistical Association, 1954
- Asymptotic Theory of Certain "Goodness of Fit" Criteria Based on Stochastic ProcessesThe Annals of Mathematical Statistics, 1952