Multiplicative, congruential random-number generators with multiplier ± 2k1 ± 2k2 and modulus 2p

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Multiplicative, congruential random-number generators with multiplier ± 2^k1 ± 2^k2 and modulus 2^p - 1

Full text

Pdf (122 KB)

Source

ACM Transactions on Mathematical Software (TOMS) archive
Volume 23 , Issue 2 (June 1997) table of contents

Pages: 255 - 265

Year of Publication: 1997

ISSN:0098-3500

Author

Pei-Chi Wu

National Chiao Tung Univ., Taiwan, China

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 20, Downloads (12 Months): 74, 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/264029.264056 What is a DOI?

ABSTRACT

The demand for random numbers in scientific applications is increasing. However, the most widely used multiplicative, congruential random-number generators with modulus 231 − 1 have a cycle length of about 2.1 × 109. Moreover, developing portable and efficient generators with a larger modulus such as 261 − 1 is more difficult than those with modulus 231 − 1. This article presents the development of multiplicative, congruential generators with modulus m = 2p − 1 and four forms of multipliers: 2k1 &minus 2k2, 2k1 + 2k2, m − 2k1 + 2k2, and m − 2k1 − 2k2, k1 > k2. The multipliers for modulus 231 − 1 and 261 − 1 are measured by spectral tests, and the best ones are presented. The generators with these multipliers are portable and vary fast. They have also passed several empirical tests, including the frequency test, the run test, and the maximum-of-t test.

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	Stuart L. Anderson, Random number generations generators on Vector supercomputers and other advanced architectures, SIAM Review, v.32 n.2, p.221-251, June 1990 [doi>10.1137/1032044]
	2	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]
	3	KIRKPATRICK, S. AND STOLE, E. 1981. A very fast shift-register sequence random number generator. J. Comput. Phys. 40, 517-526.
	4	Donald E. Knuth, The art of computer programming, volume 2 (3rd ed.): seminumerical algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1997
	5	S. K. Park , K. W. Miller, Random number generators: good ones are hard to find, Communications of the ACM, v.31 n.10, p.1192-1201, Oct. 1988 [doi>10.1145/63039.63042]
	6	W. H. Payne , J. R. Rabung , T. P. Bogyo, Coding the Lehmer pseudo-random number generator, Communications of the ACM, v.12 n.2, p.85-86, Feb. 1969 [doi>10.1145/362848.362860]
	7	Linus Schrage, A More Portable Fortran Random Number Generator, ACM Transactions on Mathematical Software (TOMS), v.5 n.2, p.132-138, June 1979 [doi>10.1145/355826.355828]
	8	SELKE, W. 1993. Cluster-flipping Monte Carlo algorithm and correlations in "good" random number generators. JETP Lett. 58, 8, 665-668.

CITED BY 8

	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
	Pierre L'Ecuyer, Uniform random number generators, Proceedings of the 30th conference on Winter simulation, p.97-104, December 13-16, 1998, Washington, D.C., United States
	Pierre L'Ecuyer , Richard Simard, Beware of linear congruential generators with multipliers of the form a = ±2q ±2r, ACM Transactions on Mathematical Software (TOMS), v.25 n.3, p.367-374, Sept. 1999
	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
	Michael Mascagni , Hongmei Chi, Parallel linear congruential generators with Sophie-Germain moduli, Parallel Computing, v.30 n.11, p.1217-1231, November 2004
	Mazen Kharbutli , Yan Solihin , Jaejin Lee, Eliminating Conflict Misses Using Prime Number-Based Cache Indexing, IEEE Transactions on Computers, v.54 n.5, p.573-586, May 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
	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, Performance

Keywords:
cycle length, efficiency, multiplicative congruential random-number generators, portability, spectral test

REVIEW

"William J. J. Rey : Reviewer"

Multiplicative congruential generators are at the root of most numeric simulations, and the computers are always hungry for pseudorandom numbers. The 32-bit-based generators are still appropriate for most users, but there is a need to go to 64 more...

Collaborative Colleagues:

Pei-Chi Wu: colleagues

Adobe Acrobat

QuickTime

Windows Media Player

Real Player