An Exhaustive Analysis of Multiplicative Congruential Random Number Generators with Modulus 2(31)-1.
NORTH CAROLINA UNIV AT CHAPEL HILL CURRICULUM IN OPERATIONS RESEARCH AND SYSTEMS ANALYSIS
Pagination or Media Count:
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 to the 31st power -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 k2,...,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 Section 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 performance 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. Author
- Statistics and Probability