François Panneton
Abstract
Fast uniform random number generators with extremely long periods have been defined and implemented based on linear recurrences modulo 2. The twisted GFSR and the Mersenne twister are famous recent examples. Besides the period length, the statistical quality of these generators is usually assessed via their equidistribution properties. The huge-period generators proposed so far are not quite optimal in this respect. In this article, we propose new generators of that form with better equidistribution and “bit-mixing” properties for equivalent period length and speed. The state of our new generators evolves in a more chaotic way than for the Mersenne twister. We illustrate how this can reduce the impact of persistent dependencies among successive output values, which can be observed in certain parts of the period of gigantic generators such as the Mersenne twister.
- Berlekamp, E. R. 1970. Factoring polynomials over large finite fields. Math. Comput. 24, 713--735.Google Scholar
- Brent, R. P., Larvala, S., and Zimmermann, P. 2003. A fast algorithm for testing reducibility of trinomials mod 2 and some new primitive trinomials of degree 3021377. Math. Comput. 72, 243, 1443--1452. Google Scholar
- Chabaud, F. and Lercier, R. 2000. A toolbox for fast computation in finite extension over finite rings. Software User's Guide. See http://zenfact.sourceforge.net/.Google Scholar
- Compagner, A. 1991. The hierarchy of correlations in random binary sequences. J. Stat. Phy. 63, 883--896.Google Scholar
- Couture, R. and L'Ecuyer, P. 2000. Lattice computations for random numbers. Math. Comput. 69, 230, 757--765. Google Scholar
- Erdmann, E. D. 1992. Empirical tests of binary keystreams. M.S. thesis, Department of Mathematics, Royal Holloway and Bedford New College, University of London.Google Scholar
- Fushimi, M. and Tezuka, S. 1983. The k-distribution of generalized feedback shift register pseudorandom numbers. Commun. ACM 26, 7, 516--523. Google Scholar
- Knuth, D. E. 1998. The Art of Computer Programming, vol. 2: Seminumerical Algorithms, 3rd ed. Addison-Wesley, Reading, Mass. Google Scholar
- L'Ecuyer, P. 1994. Uniform random number generation. Ann. Oper. Res. 53, 77--120.Google Scholar
- L'Ecuyer, P. 1996. Maximally equidistributed combined Tausworthe generators. Math. Comput. 65, 213, 203--213. Google Scholar
- L'Ecuyer, P. 1999a. Good parameters and implementations for combined multiple recursive random number generators. Oper. Res. 47, 1, 159--164. Google Scholar
- L'Ecuyer, P. 1999b. Tables of maximally equidistributed combined LFSR generators. Math. Comput. 68, 225, 261--269. Google Scholar
- L'Ecuyer, P. 2004. Random number generation. In Handbook of Computational Statistics, J. E. Gentle et al., eds. Springer Verlag, Berlin, 35--70.Google Scholar
- L'Ecuyer, P. and Panneton, F. 2002. Construction of equidistributed generators based on linear recurrences modulo 2. In Monte Carlo and Quasi-Monte Carlo Methods 2000, K.-T. Fang et al., eds. Springer Verlag, Berlin, 318--330. Google Scholar
- L'Ecuyer, P. and Simard, R. 2002. TestU01: A Software Library in ANSI C for Empirical Testing of Random Number Generators. Software User's Guide. http://www.iro.umontreal.ca/~lecuyer. Google Scholar
- Lindholm, J. H. 1968. An analysis of the pseudo-randomness properties of subsequences of long m-sequences. IEEE Trans. Inf. Theor. IT-14, 4, 569--576.Google Scholar
- Marsaglia, G. 1985. A current view of random number generators. In Computer Science and Statistics, Sixteenth Symposium on the Interface. Elsevier Science Publishers, North-Holland, Amsterdam, 3--10.Google Scholar
- Matsumoto, M. and Kurita, Y. 1994. Twisted GFSR generators II. ACM Trans. Model. Comput. Simul. 4, 3, 254--266. Google Scholar
- Matsumoto, M. and Kurita, Y. 1996. Strong deviations from randomness in m-sequences based on trinomials. ACM Trans. Model. Comput. Simul. 6, 2, 99--106. Google Scholar
- Matsumoto, M. and Nishimura, T. 1998. Mersenne twister: A 623-dimensionally equidistributed uniform pseudo-random number generator. ACM Trans. Model. Comput. Simul. 8, 1, 3--30. Google Scholar
- Niederreiter, H. 1992. Random Number Generation and Quasi-Monte Carlo Methods. SIAM CBMS-NSF Regional Conference Series in Applied Mathematics, vol. 63. SIAM, Philadelphia. Google Scholar
- Nishimura, T. 2000. Tables of 64-bit Mersenne twisters. ACM Trans. Model. Comput. Simul. 10, 4, 348--357. Google Scholar
- Panneton, F. 2004. Construction d'ensembles de points basée sur des récurrences linéaires dans un corps fini de caractéristique 2 pour la simulation Monte Carlo et l'intégration quasi-Monte Carlo. Ph.D. thesis, Département d'informatique et de recherche opérationnelle, Université de Montréal, Canada.Google Scholar
- Panneton, F. and L'Ecuyer, P. 2004. Random number generators based on linear recurrences in F2w. In Monte Carlo and Quasi-Monte Carlo Methods 2002, H. Niederreiter, ed. Springer Verlag, Berlin, 367--378. Google Scholar
- Rieke, A., Sadeghi, A.-R., and Poguntke, W. 1998. On primitivity tests for polynomials. In Proceedings of the 1998 IEEE International Symposium on Information Theory. Cambridge, Mass.Google Scholar
- Shannon, C. E. 1949. Communication theory of secrecy systems. Bell Syst. Tech. J. 28, 656--715.Google Scholar
- Tausworthe, R. C. 1965. Random numbers generated by linear recurrence modulo two. Math. Comput. 19, 201--209.Google Scholar
- Tezuka, S. 1995. Uniform Random Numbers: Theory and Practice. Kluwer Academic, Norwell, Mass.Google Scholar
- Tezuka, S. and L'Ecuyer, P. 1991. Efficient and portable combined Tausworthe random number generators. ACM Trans. Model. Comput. Simul. 1, 2, 99--112. Google Scholar
- Tootill, J. P. R., Robinson, W. D., and Eagle, D. J. 1973. An asymptotically random Tausworthe sequence. J. ACM 20, 469--481. Google Scholar
- Wang, D. and Compagner, A. 1993. On the use of reducible polynomials as random number generators. Math. Comput. 60, 363--374.Google Scholar
Index Terms
- Improved long-period generators based on linear recurrences modulo 2
Recommendations
Implementing 64-bit Maximally Equidistributed F2-Linear Generators with Mersenne Prime Period
CPUs and operating systems are moving from 32 to 64 bits, and hence it is important to have good pseudorandom number generators designed to fully exploit these word lengths. However, existing 64-bit very long period generators based on linear ...
Mersenne twister: a 623-dimensionally equidistributed uniform pseudo-random number generator
Special issue on uniform random number generationA new algorithm called Mersenne Twister (MT) is proposed for generating uniform pseudorandom numbers. For a particular choice of parameters, the algorithm provides a super astronomical period of 219937 −1 and 623-dimensional equidistribution up to 32-...
On the xorshift random number generators
G. Marsaglia recently introduced a class of very fast xorshift random number generators, whose implementation uses three “xorshift” operations. They belong to a large family of generators based on linear recurrences modulo 2, which also includes shift-...
Comments