×

Large-order multiple recursive generators with modulus \(2^{31}-1\). (English) Zbl 1462.65010

Summary: The performance of a maximum-period multiple recursive generator (MRG) depends on the choices of the recurrence order \(k\), the prime modulus \(p\), and the multipliers used. For a maximum-period MRG, a large-order \(k\) not only means a large period length (i.e., \(p^{k}- 1\)) but, more importantly, also guarantees the equidistribution property in high dimensions (i.e., up to \(k\) dimensions), a desirable feature for a good random-number generator. As to generating efficiency, in addition to the multipliers, some special choices of the prime modulus \(p\) can significantly speed up the generation of pseudo-random numbers by replacing the expensive modulo operation with efficient logical operations. To construct efficient maximum-period MRGs of a large order, we consider the prime modulus \(p = 2^{31}-1\) and, via extensive computer search, find two large values of \(k\), 7,499 and 20,897, for which \(p^{k}-1\) can be completely factorized. The successful search is achieved with the help of some results in number theory as well as some modern factorization methods. A general class of MRGs is introduced, which includes several existing classes of efficient generators. With the factorization results, we are able to identify via computer search within this class many portable and efficient maximum-period MRGs of order 7,499 or 20,897 with prime modulus \(2^{31}-1\) and multipliers of powers-of-two decomposition. These MRGs all pass the stringent TestU01 test suite empirically.

MSC:

65C10 Random number generation in numerical analysis
11K45 Pseudo-random numbers; Monte Carlo methods

Software:

TestU01; UNIRAN
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Alanen J. D., Knuth D. E.Tables of finite fields. Sankhyā Ser. A (1964) 26(4):305-328 · Zbl 0137.37502
[2] Crandall R., Pomerance C.Prime Numbers: A Computational Perspective (2000) (Springer-Verlag, New York) · Zbl 1088.11001
[3] Damgård I., Landrock P., Pomerance C.Average case error estimates for the strong probable prime test. Math. Comput. (1993) 61(203):177-194 · Zbl 0788.11059
[4] Deng L.-Y., Niederreiter H.Generalized Mersenne prime number and its application to random number generation. Monte Carlo and Quasi-Monte Carlo Methods 2002 (2004) (Springer-Verlag, Berlin) 167-180CrossRef
[5] Deng L.-Y.Efficient and portable multiple recursive generators of large order. ACM Trans. Modeling Comput. Simulation (2005) 15(1):1-13 · Zbl 1198.65025
[6] Deng L.-Y., Heinrich S., Keller A., Niederreiter H.Issues on computer search for large order multiple recursive generators. Monte Carlo and Quasi-Monte Carlo Methods 2006 (2008) (Springer-Verlag, Berlin) 251-261
[7] Deng L.-Y., Xu H.A system of high-dimensional, efficient, long-cycle and portable uniform random number generators. ACM Trans. Modeling Comput. Simulation (2003) 13(4):299-309 · Zbl 1198.65026
[8] Deng L.-Y., Li H., Shiau J.-J. H.Scalable parallel multiple recursive generators of large order. Parallel Comput. (2009) 35(1):29-37CrossRef
[9] Deng L.-Y., Guo R., Lin D. K. J., Bai F.Improving random number generators in the Monte Carlo simulations via twisting and combining. Comput. Phys. Comm. (2008a) 178(6):401-408 · Zbl 1196.65028
[10] Deng L.-Y., Li H., Shiau J.-J. H., Tsai G. H., Heinrich S., Keller A., Niederreiter H.Design and implementation of efficient and portable multiple recursive generators with few zero coefficients. Monte Carlo and Quasi-Monte Carlo Methods 2006 (2008b) (Springer-Verlag, Berlin) 263-273CrossRef
[11] Fishman G. A., Moore L. R.An exhaustive analysis of multiplicative congruential random number generators with modulus 2^{31} 1. SIAM J. Sci. Stat. Comput. (1986) 7(1):24-45 · Zbl 0603.65003
[12] Knuth D. E.The Art of Computer Programming, Volume 2: Semi-numerical Algorithms (1998) 3rd ed.(Addison-Wesley, Reading, MA) · Zbl 0895.65001
[13] L’Ecuyer P.Combined multiple recursive random number generators. Oper. Res. (1996) 44(5):816-822Link · Zbl 0904.65004
[14] L’Ecuyer P.Bad lattice structures for vectors of nonsuccessive values produced by some linear recurrences. INFORMS J. Comput. (1997) 9(1):57-60Link · Zbl 0894.65004
[15] L’Ecuyer P.Good parameters and implementations for combined multiple recursive random number generators. Oper. Res. (1999) 47(1):159-164Link · Zbl 1042.65505
[16] L’Ecuyer P., Simard R.Beware of linear congruential generators with multipliers of the form a = {\(\pm\)}2^{q} {\(\pm\)}2^{r}. ACM Trans. Math. Software (1999) 25(3):367-374 · Zbl 0964.65002
[17] L’Ecuyer P., Simard R.TestU01: A C library for empirical testing of random number generators. ACM Trans. Math. Software (2007) 33(4). Article 22 · Zbl 1365.65008
[18] L’Ecuyer P., Touzin R., Joines J. A., Barton R. R., Kang K., Fishwick P. A.Fast combined multiple recursive generators with multipliers of the form a = {\(\pm\)}2^{q} {\(\pm\)}2^{r}. Proc. 2000 Winter Simulation Conf. (2000) (IEEE Press, Pistacaway, NJ) 683-689
[19] L’Ecuyer P., Touzin R.On the Deng-Lin random number generators and related methods. Statist. Comput. (2004) 14(1):5-9
[20] L’Ecuyer P., Blouin F., Couture R.A search for good multiple recursive random number generators. ACM Trans. Modeling Comput. Simulation (1993) 3(2):87-98CrossRef · Zbl 0842.65004
[21] Lenstra H. W.Factoring integers with elliptic curves. Ann. Math. (1987) 126(2):649-673 · Zbl 0629.10006
[22] Lidl R., Niederreiter H.Introduction to Finite Fields and Their Applications (1994) revised ed.(Cambridge University Press, Cambridge, MA) · Zbl 0820.11072
[23] Marse K., Roberts S. D.Implementing a portable FORTRAN uniform (0, 1) generator. Simulation (1983) 41(4):135-139
[24] Pollard J. M.Theorems on factorization and primality testing. Proc. Cambridge Philos. Soc. (1974) 76(3):521-528 · Zbl 0294.10005
[25] Pollard J. M.A Monte Carlo method for factorization. BIT (1975) 15(3):331-334 · Zbl 0312.10006
[26] Pollard J. M., Lenstra A. K., Lenstra H. W.Factoring with cubic inetegers. The Development of Number Field Sieve (1993) 1554(Spring-Verlag, New York) 4-10Lecture Notes in Mathematics
[27] Riesel H.Prime Numbers and Computer Methods for Factorization (1994) 2nd ed.(Birkhäuser, Boston) · Zbl 0821.11001
[28] Sezgin F.Distribution of lattice points. Computing (2006) 78(2):173-193 · Zbl 1104.65007
[29] Wu P.-C.Multiplicative, congruential random-number generators with multiplier {\(\pm\)}2^{k1} {\(\pm\)}2^{k2} and modulus 2^{p} 1. ACM Trans. Math. Software (1997) 23(2):255-265 · Zbl 0887.65003
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.