Efficient and portable multiple recursive generators of large order

ABSTRACT

Deng and Xu [2003] proposed a system of multiple recursive generators of prime modulus p and order k, where all nonzero coefficients of the recurrence are equal. This type of generator is efficient because only a single multiplication is required. It is common to choose p = 2³¹−1 and some multipliers to further improve the speed of the generator. In this case, some fast implementations are available without using explicit division or multiplication. For such a p, Deng and Xu [2003] provided specific parameters, yielding the maximum period for recurrence of order k, up to 120. One problem of extending it to a larger k is the difficulty of finding a complete factorization of p^k−1. In this article, we apply an efficient technique to find k such that it is easy to factor p^k−1, with p = 2³¹−1. The largest one found is k = 1597. To find multiple recursive generators of large order k, we introduce an efficient search algorithm with an early exit strategy in case of a failed search. For k = 1597, we constructed several efficient and portable generators with the period length approximately 10^14903.1.

REFERENCES

• 1: Alanen, J. D. and Knuth, D. E. 1964. Tables of finite fields. Sankhyā, Series A 26, 305--328.
• 2: Crandall, R. and Pomerance, C. 2000. Prime Numbers---A Computational Perspective. Springer-Verlag, New York, NY.
• 3: Deng, L. Y. 2004. Generalized Mersenne prime number and its application to random number generation. In Monte Carlo and Quasi-Monte Carlo Methods 2002, H. Niederreiter, Ed. Springer-Verlag, 167--180.
• 4: Deng, L. Y., and Lin, D. K. J. 2000. Random number generation for the new century. Amer. Statist. 54, 145--150.
• 5: Lih-Yuan Deng , Hongquan Xu, A system of high-dimensional, efficient, long-cycle and portable uniform random number generators, ACM Transactions on Modeling and Computer Simulation (TOMACS), v.13 n.4, p.299-309, October 2003 [doi>10.1145/945511.945513]
• 6: Grube, A. 1973. Mehrfach rekursiv-erzeugte Pseudo-Zufallszahlen. Zeitschrift für angewandte Mathematik und Mechanik 53, 223--225.
• 7: Donald E. Knuth, The art of computer programming, volume 2 (3rd ed.): seminumerical algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1997
• 8: P. L'Ecuyer, Efficient and portable combined random number generators, Communications of the ACM, v.31 n.6, p.742-751, June 1988 [doi>10.1145/62959.62969]
• 9: L'Ecuyer, P. 1997. Bad lattice structures for vectors of non-successive values produced by some linear recurrences. INFORMS J. Comput. 9, 57--60.
• 10: 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]
• 11: Pierre L'Ecuer , François Blouin, Linear congruential generators of order K>1, Proceedings of the 20th conference on Winter simulation, p.432-439, December 12-14, 1988, San Diego, California, United States [doi>10.1145/318123.318229]
• 12: Pierre L'Ecuyer , François Blouin , Raymond Couture, A search for good multiple recursive random number generators, ACM Transactions on Modeling and Computer Simulation (TOMACS), v.3 n.2, p.87-98, April 1993 [doi>10.1145/169702.169698]
• 13: L'Ecuyer, P. and Couture, R. 1997. An implementation of the lattice and spectral tests for multiple recursive linear random number generators, INFORMS J. Comput. 9, 2, 206--217.
• 14: Pierre L'Ecuyer , Richard Simard, Beware of linear congruential generators with multipliers of the form a = ±2q ±2r, ACM Transactions on Mathematical Software (TOMS), v.25 n.3, p.367-374, Sept. 1999 [doi>10.1145/326147.326156]
• 15: Pierre L'ecuyer , Renée Touzin, On the Deng-Lin random number generators and related methods, Statistics and Computing, v.14 n.1, p.5-9, January 2004 [doi>10.1023/B:STCO.0000009417.88960.81]
• 16: Lehmer, D. H. 1951. Mathematical methods in large-scale computing units. Proceedings of the 2nd Symposium on Large Scale Digital Computing Machinery. Harvard University Press, Cambridge, MA, 141--146.
• 17: Rudolf Lidl , Harald Niederreiter, Introduction to finite fields and their applications, Cambridge University Press, New York, NY, 1986
• 18: Marsaglia, G. 1996. The Marsaglia random number CDROM including the DIEHARD battery of tests of randomness. See http://stat.fsu.edu/pub/diehard.
• 19: 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]
• 20: 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:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.1 Numerical Algorithms and Problems
          Subjects: Computations in finite fields

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

General Terms:
Algorithms, Design, Performance

Keywords:
DX-k generator, GMP, MRG, irreducible polynomial, linear congruential generator, primitive polynomial.