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
MathSciNet review: 993929
Full-text PDF Free Access

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?)

Similar Articles

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

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

Additional Information

Keywords: Congruential generator, discrepancy, random number generation, spectral test
Article copyright: © Copyright 1990 American Mathematical Society