Efficient and portable combined Tausworthe random number generators

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Efficient and portable combined Tausworthe random number generators

Full text

Pdf (773 KB)

Source

ACM Transactions on Modeling and Computer Simulation (TOMACS) archive
Volume 1 , Issue 2 (April 1991) table of contents

Pages: 99 - 112

Year of Publication: 1991

ISSN:1049-3301

Authors

Shu Tezuka	IBM Research, Tokyo, Japan
Pierre L'Ecuyer	Univ. de Montreal, Montreal, P.Q., Canada

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 10, Downloads (12 Months): 61, Citation Count: 11

Additional Information:

references cited by index terms review collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/116890.116892 What is a DOI?

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	ANDRe, D. A., MULLEN, G. L., AND NIEDERREITER, H. Figures of merit for digital multistep pseudorandom numbers. Math. Comput. 54 (1990), 737-748.
	2	Paul Bratley , Bennett L. Fox , Linus E. Schrage, A guide to simulation (2nd ed.), Springer-Verlag New York, Inc., New York, NY, 1987
	3	George A Fishman , Louis R Moore, III, An exhaustive analysis of multiplicative congruential random number generators with modulus 2³¹-1, SIAM Journal on Scientific and Statistical Computing, v.7 n.1, p.24-45, Jan. 1986 [doi>10.1137/0907002]
	4	Masanori Fushimi, Designing a uniform random number generator whose subsequences are k-distributed, SIAM Journal on Computing, v.17 n.1, p.89-99, Feb. 1988 [doi>10.1137/0217006]
	5	Donald E. Knuth, The art of computer programming, volume 2 (3rd ed.): seminumerical algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1997
	6	P. L'Ecuyer, Efficient and portable combined random number generators, Communications of the ACM, v.31 n.6, p.742-751, June 1988 [doi>10.1145/62959.62969]
	7	Pierre L'Ecuyer, Random numbers for simulation, Communications of the ACM, v.33 n.10, p.85-97, Oct. 1990 [doi>10.1145/84537.84555]
	8	L'EcuYER, P., AND TEZUKA, S. Structural properties for two classes of combined random number generators. To appear in Math. Comput. 1991.
	9	LENSTRA, A. K. Factoring multivariate polynomials over finite fields. J. Comput. Syst. Sci. 30 (1985), 235-248.
	10	Rudolf Lidl , Harald Niederreiter, Introduction to finite fields and their applications, Cambridge University Press, New York, NY, 1986
	11	MARSAGLIA, G. The structure of linear congruential sequences. In Appltcatzons of Number Theory to Numerical Analysis. Academic Press, New York, 1972, 249-285.
	12	MARSAGLIA, G. A current view of random number generators. In Computer Science and Statistics: Interface. Elsevier Science, North-Holland, New York, 1985, 3-10.
	13	MARSAGLIA, G., ZAMAN, A., AND TSANG, W. W. Towards a Universal Random Number Generator. Stat. Prob. Letters. 8 (1990), 35-39.
	14	G. L. Mullen , H. Niederreiter, Optimal characteristic polynomials for digital multistep Pseudorandom numbers, Computing, v.39 n.2, p.155-163, April 1, 1987 [doi>10.1007/BF02310104]
	15	Harald Niederreiter, A statistical analysis of generalized feedback shift register pseudorandom number generators, SIAM Journal on Scientific and Statistical Computing, v.8 n.6, p.1035-1051, November 1, 1987 [doi>10.1137/0908084]
	16	NIEDERREITER, a. Point sets and sequences with small discrepancy. Monatsh. Math. 104 (1987), 273-337.
	17	NIEDERREITER, H. The serial test for digital k-step pseudorandom numbers. Math. J. Okayama Univ. 30 (1988), 93-119.
	18	Harald Niederreiter, Recent trends in random number and random vector generation, Annals of Operations Research, v.31 n.1-4, p.323-346, June 1991 [doi>10.1007/BF02204856]
	19	TAUSWORTHE, R. C. Random numbers generated by linear recurrence modulo two. Math. Comput. 19 (1965), 201-209.
	20	Shu Tezuka, Walsh-spectral test for GFSR pseudorandom numbers, Communications of the ACM, v.30 n.8, p.731-735, Aug. 1987 [doi>10.1145/27651.27657]
	21	Shu Tezuka, On the discrepancy of GFSR pseudorandom numbers, Journal of the ACM (JACM), v.34 n.4, p.939-949, Oct. 1987 [doi>10.1145/31846.31848]
	22	TEZUKA, S. Random number generation based on polynomial arithmetic modulo two. IBM TRL Res. Rep. TR-0017, 1989
	23	Shu Tezuka, Lattice structure of pseudorandom sequences from shift-register generators, Proceedings of the 22nd conference on Winter simulation, p.266-269, December 09-12, 1990, New Orleans, Louisiana, United States
	24	J. P. R. Tootill , W. D. Robinson , A. G. Adams, The Runs Up-and-Down Performance of Tausworthe Pseudo-Random Number Generators, Journal of the ACM (JACM), v.18 n.3, p.381-399, July 1971 [doi>10.1145/321650.321655]
	25	J. P. R. Tootill , W. D. Robinson , D. J. Eagle, An Asymptotically Random Tausworthe Sequence, Journal of the ACM (JACM), v.20 n.3, p.469-481, July 1973 [doi>10.1145/321765.321778]
	26	WICHMANN, B. A., AND HILL, I.D. An efficient and portable pseudorandom number generator. Appl. Stat. 31 (1982), 188 190.

CITED BY 11

	Makoto Matsumoto , Takuji Nishimura, Mersenne twister: a 623-dimensionally equidistributed uniform pseudo-random number generator, ACM Transactions on Modeling and Computer Simulation (TOMACS), v.8 n.1, p.3-30, Jan. 1998
	Pierre L'Ecuyer, Uniform random number generators: a review, Proceedings of the 29th conference on Winter simulation, p.127-134, December 07-10, 1997, Atlanta, Georgia, United States
	Ora E. Percus , Paula A. Whitlock, Theory and application of Marsaglia's monkey test for pseudorandom number generators, ACM Transactions on Modeling and Computer Simulation (TOMACS), v.5 n.2, p.87-100, April 1995
	Makoto Matsumoto , Yoshiharu Kurita, Strong deviations from randomness in m-sequences based on trinomials, ACM Transactions on Modeling and Computer Simulation (TOMACS), v.6 n.2, p.99-106, April 1996
	Piere L'Ecuyer , Christiane Lemieux, Quasi-Monte Carlo via linear shift-register sequences, Proceedings of the 31st conference on Winter simulation: Simulation---a bridge to the future, p.632-639, December 05-08, 1999, Phoenix, Arizona, United States
	M. M. Ali , A. Törn, Population set-based global optimization algorithms: some modifications and numerical studies, Computers and Operations Research, v.31 n.10, p.1703-1725, September 2004
	Pierre L'Ecuyer , Francois Panneton, A new class of linear feedback shift register generators, Proceedings of the 32nd conference on Winter simulation, December 10-13, 2000, Orlando, Florida
	François Panneton , Pierre L'ecuyer , Makoto Matsumoto, Improved long-period generators based on linear recurrences modulo 2, ACM Transactions on Mathematical Software (TOMS), v.32 n.1, p.1-16, March 2006
	Pierre L'Ecuyer , François Panneton, Fast random number generators based on linear recurrences modulo 2: overview and comparison, Proceedings of the 37th conference on Winter simulation, December 04-07, 2005, Orlando, Florida
	Kimmo Vehkalahti , Simo Puntanen , Lauri Tarkkonen, Effects of measurement errors in predictor selection of linear regression model, Computational Statistics & Data Analysis, v.52 n.2, p.1183-1195, October, 2007
	M. M. Ali , A. Törn , S. Viitanen, A Numerical Comparison of Some Modified Controlled Random SearchAlgorithms, Journal of Global Optimization, v.11 n.4, p.377-385, December 1997

INDEX TERMS

Primary Classification:
G. Mathematics of Computing
G.3 PROBABILITY AND STATISTICS
Subjects: Random number generation

General Terms:
Algorithms, Performance, Theory

REVIEW

"Gary Carlson : Reviewer"

The authors write about pseudorandom number generators as though they are generating true random numbers. As the techniques get better and better, it is easy to talk about “random number generators,” but we must be careful to keep more...

Collaborative Colleagues:

Shu Tezuka: colleagues

Pierre L'Ecuyer: colleagues

Adobe Acrobat

QuickTime

Windows Media Player

Real Player