Beware of linear congruential generators with multipliers of the form a = ±2q ±2r

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Beware of linear congruential generators with multipliers of the form a = ±2q ±2r

Full text

Pdf (102 KB)

Source

ACM Transactions on Mathematical Software (TOMS) archive
Volume 25 , Issue 3 (September 1999) table of contents

Pages: 367 - 374

Year of Publication: 1999

ISSN:0098-3500

Authors

Pierre L'Ecuyer	Univ. de Montréal, Montréal, P.Q., Canada
Richard Simard	Univ. de Montréal, Montréal, P.Q., Canada

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 6, Downloads (12 Months): 35, Citation Count: 8

Additional Information:

abstract 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/326147.326156 What is a DOI?

ABSTRACT

Linear congruential random-number generators with Mersenne prime modulus and multipliers of the form a = ±2q ±r have been proposed recently. Their main advantage is the availability of a simple and fast implementation algorithm for such multipliers. This note generalizes this algorithm, points out statistical weaknesses of these multipliers when used in a straightforward manner, and suggests in what context they could be used safely.

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	COMPAGNER, A. 1995. Operational conditions for random number generation. Phys. Rev. E52, 5-B, 5634-5645.
	2	FISHMAN, G. 1996. Monte Carlo: Concepts, Algorithms, and Applications. In Operations Research Springer Series on Operations Research, vol. 1. Springer-Verlag, New York, NY.
	3	Donald E. Knuth, The art of computer programming, volume 2 (3rd ed.): seminumerical algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1997
	4	L'ECUYER, P. 1996. Combined multiple recursive random number generators. Oper. Res. 44, 5, 816-822.
	5	L'ECUYER, P. 1998. Random number generation. In Handbook of Simulation, J. Banks, Ed. John Wiley & Sons, Inc., New York, NY, 93-137.
	6	Gregory W. Fischer , Ziv Carmon , Dan Ariely , Gal Zauberman , Pierre L'Ecuyer, Good Parameters and Implementations for Combined Multiple Recursive Random Number Generators, Operations Research, v.47 n.1, p.159-164, January 1999 [doi>10.1287/opre.47.1.159]
	7	Pierre L'Ecuyer, Tables of linear congruential generators of different sizes and good lattice structure, Mathematics of Computation, v.68 n.225, p.249-260, Jan. 1999 [doi>10.1090/S0025-5718-99-00996-5]
	8	Harald Niederreiter, Random number generation and quasi-Monte Carlo methods, Society for Industrial and Applied Mathematics, Philadelphia, PA, 1992
	9	WEGENKITTL, S. 1998. Generalized f-divergence and frequency analysis in Markov chains. Ph.D. Dissertation. Univ. of Salzburg. Available via http://random.mat.sbg.ac.at/team/.
	10	Pei-Chi Wu, Multiplicative, congruential random-number generators with multiplier ± 2^k1 ± 2^k2 and modulus 2^p - 1, ACM Transactions on Mathematical Software (TOMS), v.23 n.2, p.255-265, June 1997 [doi>10.1145/264029.264056]

CITED BY 8

	Pei-Chi Wu, Random number generation with primitive pentanomials, ACM Transactions on Modeling and Computer Simulation (TOMACS), v.11 n.4, p.346-351, October 2001
	Lih-Yuan Deng , Hongquan Xu, A system of high-dimensional, efficient, long-cycle and portable uniform random number generators, ACM Transactions on Modeling and Computer Simulation (TOMACS), v.13 n.4, p.299-309, October 2003
	Pierre L'Ecuyer , Renée Touzin, Fast combined multiple recursive generators with multipliers of the form a = ±2^q ±2^r, Proceedings of the 32nd conference on Winter simulation, December 10-13, 2000, Orlando, Florida
	François Panneton , Pierre L'ecuyer, On the xorshift random number generators, ACM Transactions on Modeling and Computer Simulation (TOMACS), v.15 n.4, p.346-361, October 2005
	Lih-Yuan Deng, Efficient and portable multiple recursive generators of large order, ACM Transactions on Modeling and Computer Simulation (TOMACS), v.15 n.1, p.1-13, January 2005
	Peter Hellekalek , Stefan Wegenkittl, Empirical evidence concerning AES, ACM Transactions on Modeling and Computer Simulation (TOMACS), v.13 n.4, p.322-333, October 2003
	Pierre L'Ecuyer, Software for uniform random number generation: distinguishing the good and the bad, Proceedings of the 33nd conference on Winter simulation, December 09-12, 2001, Arlington, Virginia
	Pierre L'Ecuyer , Richard Simard, TestU01: A C library for empirical testing of random number generators, ACM Transactions on Mathematical Software (TOMS), v.33 n.4, p.22-es, August 2007

INDEX TERMS

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

Additional Classification:
G. Mathematics of Computing
G.4 MATHEMATICAL SOFTWARE
Subjects: Algorithm design and analysis

General Terms:
Algorithms, Experimentation, Measurement, Performance

Keywords:
correlation test, linear congruential generators, random number generation

REVIEW

"John B. Slater : Reviewer"

Pseudo-random number generators based on linear congruence relations using a congruence base of a Mersenne prime (one that is one less than a power of two) and a multiplier obtained from the sum or difference of two powers of two have been pro more...

Collaborative Colleagues:

Pierre L'Ecuyer: colleagues

Richard Simard: colleagues

Adobe Acrobat

QuickTime

Windows Media Player

Real Player