Beware of linear congruential generators with multipliers of the form a = ±2q ±2r

ABSTRACT

Linear congruential random-number generators with Mersenne prime modulus and multipliers of the form a = ±2q ±r have been proposed recently. Their main advantage is the availability of a simple and fast implementation algorithm for such multipliers. This note generalizes this algorithm, points out statistical weaknesses of these multipliers when used in a straightforward manner, and suggests in what context they could be used safely.

REFERENCES

• 1: COMPAGNER, A. 1995. Operational conditions for random number generation. Phys. Rev. E52, 5-B, 5634-5645.
• 2: FISHMAN, G. 1996. Monte Carlo: Concepts, Algorithms, and Applications. In Operations Research Springer Series on Operations Research, vol. 1. Springer-Verlag, New York, NY.
• 3: Donald E. Knuth, The art of computer programming, volume 2 (3rd ed.): seminumerical algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1997
• 4: L'ECUYER, P. 1996. Combined multiple recursive random number generators. Oper. Res. 44, 5, 816-822.
• 5: L'ECUYER, P. 1998. Random number generation. In Handbook of Simulation, J. Banks, Ed. John Wiley & Sons, Inc., New York, NY, 93-137.
• 6: Gregory W. Fischer , Ziv Carmon , Dan Ariely , Gal Zauberman , Pierre L'Ecuyer, Good Parameters and Implementations for Combined Multiple Recursive Random Number Generators, Operations Research, v.47 n.1, p.159-164, January 1999 [doi>10.1287/opre.47.1.159]
• 7: Pierre L'Ecuyer, Tables of linear congruential generators of different sizes and good lattice structure, Mathematics of Computation, v.68 n.225, p.249-260, Jan. 1999 [doi>10.1090/S0025-5718-99-00996-5]
• 8: Harald Niederreiter, Random number generation and quasi-Monte Carlo methods, Society for Industrial and Applied Mathematics, Philadelphia, PA, 1992
• 9: WEGENKITTL, S. 1998. Generalized f-divergence and frequency analysis in Markov chains. Ph.D. Dissertation. Univ. of Salzburg. Available via http://random.mat.sbg.ac.at/team/.
• 10: Pei-Chi Wu, Multiplicative, congruential random-number generators with multiplier ± 2^k1 ± 2^k2 and modulus 2^p - 1, ACM Transactions on Mathematical Software (TOMS), v.23 n.2, p.255-265, June 1997 [doi>10.1145/264029.264056]

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, Experimentation, Measurement, Performance

Keywords:
correlation test, linear congruential generators, random number generation