Multiplicative, congruential random-number generators with multiplier ± 2k1 ± 2k2 and modulus 2p - 1

ABSTRACT

The demand for random numbers in scientific applications is increasing. However, the most widely used multiplicative, congruential random-number generators with modulus 231 − 1 have a cycle length of about 2.1 × 109. Moreover, developing portable and efficient generators with a larger modulus such as 261 − 1 is more difficult than those with modulus 231 − 1. This article presents the development of multiplicative, congruential generators with modulus m = 2p − 1 and four forms of multipliers: 2k1 &minus 2k2, 2k1 + 2k2, m − 2k1 + 2k2, and m − 2k1 − 2k2, k1 > k2. The multipliers for modulus 231 − 1 and 261 − 1 are measured by spectral tests, and the best ones are presented. The generators with these multipliers are portable and vary fast. They have also passed several empirical tests, including the frequency test, the run test, and the maximum-of-t test.

REFERENCES

• 1: Stuart L. Anderson, Random number generations generators on Vector supercomputers and other advanced architectures, SIAM Review, v.32 n.2, p.221-251, June 1990 [doi>10.1137/1032044]
• 2: George A Fishman , Louis R Moore, III, An exhaustive analysis of multiplicative congruential random number generators with modulus 2³¹-1, SIAM Journal on Scientific and Statistical Computing, v.7 n.1, p.24-45, Jan. 1986 [doi>10.1137/0907002]
• 3: KIRKPATRICK, S. AND STOLE, E. 1981. A very fast shift-register sequence random number generator. J. Comput. Phys. 40, 517-526.
• 4: Donald E. Knuth, The art of computer programming, volume 2 (3rd ed.): seminumerical algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1997
• 5: S. K. Park , K. W. Miller, Random number generators: good ones are hard to find, Communications of the ACM, v.31 n.10, p.1192-1201, Oct. 1988 [doi>10.1145/63039.63042]
• 6: W. H. Payne , J. R. Rabung , T. P. Bogyo, Coding the Lehmer pseudo-random number generator, Communications of the ACM, v.12 n.2, p.85-86, Feb. 1969 [doi>10.1145/362848.362860]
• 7: Linus Schrage, A More Portable Fortran Random Number Generator, ACM Transactions on Mathematical Software (TOMS), v.5 n.2, p.132-138, June 1979 [doi>10.1145/355826.355828]
• 8: SELKE, W. 1993. Cluster-flipping Monte Carlo algorithm and correlations in "good" random number generators. JETP Lett. 58, 8, 665-668.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.3 PROBABILITY AND STATISTICS
      Subjects: Random number generation

Additional Classification:
  G. Mathematics of Computing
  G.4 MATHEMATICAL SOFTWARE
      Subjects: Algorithm design and analysis

General Terms:
Algorithms, Performance

Keywords:
cycle length, efficiency, multiplicative congruential random-number generators, portability, spectral test