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

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.