Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)



Maximally Equidistributed
Combined Tausworthe Generators

Author: Pierre L’Ecuyer
Journal: Math. Comp. 65 (1996), 203-213
MSC (1991): Primary 65C10
MathSciNet review: 1325871
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: Tausworthe random number generators based on a primitive trinomial allow an easy and fast implementation when their parameters obey certain restrictions. However, such generators, with those restrictions, have bad statistical properties unless we combine them. A generator is called maximally equidistributed if its vectors of successive values have the best possible equidistribution in all dimensions. This paper shows how to find maximally equidistributed combinations in an efficient manner, and gives a list of generators with that property. Such generators have a strong theoretical support and lend themselves to very fast software implementations.

References [Enhancements On Off] (What's this?)

  • 1 A. Compagner, The hierarchy of correlations in random binary sequences, J. Statist. Phys. 63 (1991), 883--896. MR 93c:65012
  • 2 R. Couture, P. L'Ecuyer, and S. Tezuka, On the distribution of $k$-dimensional vectors for simple and combined Tausworthe sequences, Math. Comp. 60 (1993), 749--761 and S11--S16. MR 93h:11085
  • 3 D. E. Knuth, The art of computer programming: Seminumerical algorithms, Vol. 2, 2nd ed., Addison-Wesley, Reading, MA, 1981. MR 83i:68003
  • 4 P. L'Ecuyer, Efficient and portable combined random number generators, Comm. ACM 31 (1988), 742--749 and 774. See also the correspondence in the same journal, 32 (1989), 1019--1024. MR 89d:65005
  • 5 ------, Testing random number generators, Proc. 1992 Winter Simulation Conference, IEEE Press, Pistacaway, NJ, 1992, pp. 305--313.
  • 6 ------, Uniform random number generation, Ann. Oper. Res. 53 (1994), 77--120. CMP 95:06
  • 7 J. H. Lindholm, An analysis of the pseudo-randomness properties of subsequences of long $m$-sequences, IEEE Trans. Inform. Theory IT-14 (1968), 569--576.
  • 8 H. Niederreiter, Random number generation and quasi-Monte Carlo methods, SIAM CBMS-NSF Regional Conf. Series in Appl. Math., vol. 63, SIAM, Philadelphia, PA, 1992. MR 93h:65008
  • 9 R. C. Tausworthe, Random numbers generated by linear recurrence modulo two, Math. Comp. 19 (1965), 201--209. MR 32:1878
  • 10 S. Tezuka, Random number generation based on polynomial arithmetic modulo two, IBM TRL Research Report, RT-0017, 1989.
  • 11 S. Tezuka and P. L'Ecuyer, Efficient and portable combined Tausworthe random number generators, ACM Trans. Model. Comput. Simulation 1 (1991), 99--112.
  • 12 J. P. R. Tootill, W. D. Robinson, and D. J. Eagle, An asymptotically random Tausworthe sequence, J. Assoc. Comput. Mach. 20 (1973), 469--481.
  • 13 D. Wang and A. Compagner, On the use of reducible polynomials as random number generators, Math. Comp. 60 (1993), 363--374. MR 93e:65012
  • 14 N. Zierler and J. Brillhart, On primitive trinomials (Mod 2), Inform. and Control 13 (1968), 541--554,

Similar Articles

Retrieve articles in Mathematics of Computation of the American Mathematical Society with MSC (1991): 65C10

Retrieve articles in all journals with MSC (1991): 65C10

Additional Information

Pierre L’Ecuyer
Affiliation: Département d’Informatique et de Recherche Opérationnelle, Université de Montréal, C.P. 6128, Succ. Centre-Ville, Montréal, H3C 3J7, Canada

Keywords: Random number generation, equidistribution, combined generators
Received by editor(s): October 18, 1994
Article copyright: © Copyright 1996 American Mathematical Society

American Mathematical Society