Maximally equidistributed combined Tausworthe generators

L’Ecuyer, Pierre

doi:10.1090/S0025-5718-96-00696-5

Maximally equidistributed combined Tausworthe generators
HTML articles powered by AMS MathViewer

by Pierre L’Ecuyer PDF

Math. Comp. 65 (1996), 203-213 Request permission

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

Aaldert Compagner, The hierarchy of correlations in random binary sequences, J. Statist. Phys. 63 (1991), no. 5-6, 883–896. MR 1116039, DOI 10.1007/BF01029989
Raymond Couture, Pierre L’Ecuyer, and Shu Tezuka, On the distribution of $k$-dimensional vectors for simple and combined Tausworthe sequences, Math. Comp. 60 (1993), no. 202, 749–761, S11–S16. MR 1176708, DOI 10.1090/S0025-5718-1993-1176708-4
Donald E. Knuth, The art of computer programming. Vol. 2, 2nd ed., Addison-Wesley Series in Computer Science and Information Processing, Addison-Wesley Publishing Co., Reading, Mass., 1981. Seminumerical algorithms. MR 633878
Pierre L’Ecuyer, Efficient and portable combined random number generators, Comm. ACM 31 (1988), no. 6, 742–749, 774. MR 945034, DOI 10.1145/62959.62969
—, Testing random number generators, Proc. 1992 Winter Simulation Conference, IEEE Press, Pistacaway, NJ, 1992, pp. 305–313.
—, Uniform random number generation, Ann. Oper. Res. 53 (1994), 77–120.
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.
Harald Niederreiter, Random number generation and quasi-Monte Carlo methods, CBMS-NSF Regional Conference Series in Applied Mathematics, vol. 63, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 1992. MR 1172997, DOI 10.1137/1.9781611970081
Robert C. Tausworthe, Random numbers generated by linear recurrence modulo two, Math. Comp. 19 (1965), 201–209. MR 184406, DOI 10.1090/S0025-5718-1965-0184406-1
S. Tezuka, Random number generation based on polynomial arithmetic modulo two, IBM TRL Research Report, RT-0017, 1989.
S. Tezuka and P. L’Ecuyer, Efficient and portable combined Tausworthe random number generators, ACM Trans. Model. Comput. Simulation 1 (1991), 99–112.
J. P. R. Tootill, W. D. Robinson, and D. J. Eagle, An asymptotically random Tausworthe sequence, J. Assoc. Comput. Mach. 20 (1973), 469–481.
Da Kai Wang and Aaldert Compagner, On the use of reducible polynomials as random number generators, Math. Comp. 60 (1993), no. 201, 363–374. MR 1155576, DOI 10.1090/S0025-5718-1993-1155576-0
Neal Zierler and John Brillhart, On primitive trinomials $(\textrm {mod}\ 2)$. II, Information and Control 14 (1969), 566–569. MR 244204, DOI 10.1016/S0019-9958(69)90356-8