|
Maximally Equidistributed Combined Tausworthe Generators
Author(s):
Pierre
L'Ecuyer.
Journal:
Math. Comp.
65
(1996),
203-213.
MSC (1991):
Primary 65C10
Retrieve article in:
PDF
This article is available free of charge
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:
- 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
 -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
 -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
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
Email:
lecuyer@iro.umontreal.ca
DOI:
10.1090/S0025-5718-96-00696-5
PII:
S 0025-5718(96)00696-5
Keywords:
Random number generation,
equidistribution,
combined generators
Received by editor(s):
October 18, 1994
Copyright of article:
Copyright
1996,
American Mathematical Society
|
Comments: webmaster@ams.org