Coding the Lehmer pseudo-random number generator

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Coding the Lehmer pseudo-random number generator

Full text

Pdf (335 KB)

Source

Communications of the ACM archive
Volume 12 , Issue 2 (February 1969) table of contents

Pages: 85 - 86

Year of Publication: 1969

ISSN:0001-0782

Authors

W. H. Payne	Washington State Univ., Pullman
J. R. Rabung	Washington State Univ., Pullman
T. P. Bogyo	Washington State Univ., Pullman

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 7, Downloads (12 Months): 79, Citation Count: 18

Additional Information:

abstract references cited by index terms 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/362848.362860 What is a DOI?

ABSTRACT

An algorithm and coding technique is presented for quick evaluation of the Lehmer pseudo-random number generator modulo 2 ** 31 - 1, a prime Mersenne number which produces 2 ** 31 - 2 numbers, on a p-bit (greater than 31) computer. The computation method is extendible to limited problems in modular arithmetic. Prime factorization for 2 ** 61 - 2 and a primitive root for 2 ** 61 - 1, the next largest prime Mersenne number, are given for possible construction of a pseudo-random number generator of increased cycle length.

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	A. Van Gelder, Some New Results in Pseudo-Random Number Generation, Journal of the ACM (JACM), v.14 n.4, p.785-792, Oct. 1967 [doi>10.1145/321420.321437]
	2	LEHMER, D.H. Random number generation on the BRL highspeed computing machines, by M. L. Juncosa. Math. Rev. 15 (1954), 559.
	3	K. D Tocher, The art of simulation, English Universities Press, 1967
	4	Random number generation and testing. Form C20-8011, IBM, 1959.

CITED BY 18

	Karl Entacher, Bad subsequences of well-known linear congruential pseudorandom number generators, ACM Transactions on Modeling and Computer Simulation (TOMACS), v.8 n.1, p.61-70, Jan. 1998
	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
	Pierre L'Ecuyer , Serge Côté, Implementing a random number package with splitting facilities, ACM Transactions on Mathematical Software (TOMS), v.17 n.1, p.98-111, March 1991
	P. L'Ecuyer, Efficient and portable combined random number generators, Communications of the ACM, v.31 n.6, p.742-751, June 1988
	Diane Crawford, Technical correspondence, Communications of the ACM, v.36 n.7, p.105, July 1993
	David F. Carta, Two fast implementations of the “minimal standard” random number generator, Communications of the ACM, v.33 n.1, p.87-88, Jan. 1990
	Lih-Yuan Deng , Cecil Rousseau , Yilian Yuan, Generalized Lehmer-Tausworthe random number generators, Proceedings of the 30th annual Southeast regional conference, April 08-10, 1992, Raleigh, North Carolina
	Linus Schrage, A More Portable Fortran Random Number Generator, ACM Transactions on Mathematical Software (TOMS), v.5 n.2, p.132-138, June 1979
	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
	George S. Fishman , Louis R. Moore, An exhaustive search for optimal multipliers, Proceedings of the 16th conference on Winter simulation, p.198-200, December 28-30, 1984, Dallas, TX
	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
	W. Hörmann , G. Derflinger, A portable random number generator well suited for the rejection method, ACM Transactions on Mathematical Software (TOMS), v.19 n.4, p.489-495, Dec. 1993
	D. Guinier, A fast uniform astronomical random number generator, ACM SIGSAC Review, v.7 n.1, p.1-12, Spring 1989
	Daniel Guinier, A fast and portable uniform quasi-random generator of very large period based ona generalized multi-moduli congruential method, ACM SIGSIM Simulation Digest, v.19 n.3, p.27-33, Sept. 1988
	R. Durán Díaz , J. Muñoz Masqué, Optimal strong primes, Information Processing Letters, v.93 n.1, p.47-52, 16 January 2005
	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
	Some test results on the SIMSCRIPT II. 5 and SIMPL/1 pseudorandom number generators, ACM SIGSIM Simulation Digest, v.8 n.1, p.79-84, October 1976