A Statistical Evaluation of Multiplicative Congruential Random Number Generators with Modulus 2³¹ — 1

Abstract

This article presents the results of empirically testing 16 alternative multipliers for a multiplicative congruential random number generator with modulus 2³¹ — 1. Two of the multipliers are in common use, six are the best of 50 candidate multipliers according to the theoretical spectral and lattice tests, and eight are the worst, with regard to 2-tuples, among the 50. The test results raise serious doubts about several of the multipliers, including one in common use. The tests were also applied to a well-known theoretically poor generator, RANDU, and gave strong empirical evidence of its inadequacy. Since comparison of the results of the First eight multipliers with those for the eight worst multipliers failed to show any apparent gross differences, one may want to relax the currently employed stringent criteria for acceptable performance on the lattice and spectral tests.

Key Words:

• Random number generation
• Congruential generator
• Lattice test
• Spectral test
• Runs test