Fourier Analysis of Uniform Random Number Generators

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Fourier Analysis of Uniform Random Number Generators

Full text

Pdf (1.29 MB)

Source

Journal of the ACM (JACM) archive
Volume 14 , Issue 1 (January 1967) table of contents

Pages: 100 - 119

Year of Publication: 1967

ISSN:0004-5411

Authors

R. R. Coveyou	Swarthmore College, Swarthmore, Pennsylvania and Oak Ridge National Laboratory, Oak Ridge, Tennessee
R. D. Macpherson	Swarthmore College, Swarthmore, Pennsylvania and Oak Ridge National Laboratory, Oak Ridge, Tennessee

Publisher

ACM New York, NY, USA

Bibliometrics

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

Additional Information:

abstract references cited by index terms collaborative colleagues peer to peer

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

ABSTRACT

A method of analysis of uniform random number generators is developed, applicable to almost all practical methods of generation. The method is that of Fourier analysis of the output sequences of such generators. With this tool it is possible to understand and predict relevant statistical properties of such generators and compare and evaluate such methods. Many such analyses and comparisons have been carried out. The performance of these methods as implemented on differing computers is also studied. The main practical conclusions of the study are: (a) Such a priori analysis and prediction of statistical behavior of uniform random number generators is feasible. (b) The commonly used multiplicative congruence method of generation is satisfactory with careful choice of the multiplier for computers with an adequate (≥ ∼ 35-bit) word length. (c) Further work may be necessary on generators to be used on machines of shorter word 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	J. Certaine, On Sequences of Pseudo-Random Numbers of Maximal Length, Journal of the ACM (JACM), v.5 n.4, p.353-356, Oct. 1958 [doi>10.1145/320941.320949]
	2	M. Donald MacLaren , George Marsaglia, Uniform Random Number Generators, Journal of the ACM (JACM), v.12 n.1, p.83-89, Jan. 1965 [doi>10.1145/321250.321257]
	3	MOIRDELL, L.J. Observation on the minimum of a quadratic form in eight variables. J. London Math. Soc. 19 (1944), 3-6.
	4	CASSLS, J. W: S. An Introduction to the Geometry of Numbers. Springer-Verlag, Berlin, 1959, pp. 31,332. (This contains proofs of theorems referred to in the text.)
	5	R. R. Coveyou, Serial Correlation in the Generation of Pseudo-Random Numbers, Journal of the ACM (JACM), v.7 n.1, p.72-74, Jan. 1960 [doi>10.1145/321008.321018]
	6	Martin Greenberger, Method in randomness, Communications of the ACM, v.8 n.3, p.177-179, March 1965 [doi>10.1145/363791.363827]
	7	HULL, W..E., AND DOBELL, A.R. Random number generators. SIAM Rev. 4 (1962), 229- 254. (This contains a good survey of the field and a comprehensive bibliography.)
	8	JANSSON, B. Autocorrelations between pseudo-random numbers. NordisK Tidskr. Informations-Behandling 4 (1964), 6-27.
	9	WEYL, H. Uber die Gleichverteilung yon Zahlen rood Eins. Math. Ann. 77 (1916); also Selecta Hermann Weyl. Birkhauser Verlag, Basel, 1956, p. 111. (This contains proofs of theorems referred to in the text.)

CITED BY 37

	T. G. Lewis , W. H. Payne, Generalized Feedback Shift Register Pseudorandom Number Algorithm, Journal of the ACM (JACM), v.20 n.3, p.456-468, July 1973
	Mark Goresky , Andrew Klapper, Efficient multiply-with-carry random number generators with maximal period, ACM Transactions on Modeling and Computer Simulation (TOMACS), v.13 n.4, p.310-321, October 2003
	J. B. Kruskal, Extremely portable random number generator, Communications of the ACM, v.12 n.2, p.93-94, Feb. 1969
	Hannes Leeb, Asymptotic properties of the spectral test, diaphony, and related quantities, Mathematics of Computation, v.71 n.237, p.297-309, January 2002
	George Marsaglia , T. A. Bray, One-line random number generators and their use in combinations, Communications of the ACM, v.11 n.11, p.757-759, Nov. 68
	Shu Tezuka, Walsh-spectral test for GFSR pseudorandom numbers, Communications of the ACM, v.30 n.8, p.731-735, Aug. 1987
	Peter Hellekalek , Harald Niederreiter, The weighted spectral test: diaphony, ACM Transactions on Modeling and Computer Simulation (TOMACS), v.8 n.1, p.43-60, Jan. 1998
	Hui-Chin Tang, An exhaustive analysis of two-term multiple recursive random number generators with efficient multipliers, Journal of Computational and Applied Mathematics, v.192 n.2, p.411-416, 1 August 2006
	James E. Gentle, Simulation and analysis with IMSL routines, Proceedings of the 18th conference on Winter simulation, p.223-226, December 08-10, 1986, Washington, D.C., United States
	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
	C. S. Smith, Multiplicative Pseudo-Random Number Generators with Prime Modulus, Journal of the ACM (JACM), v.18 n.4, p.586-593, Oct. 1971
	Karl Entacher, Parallel streams of linear random numbers in the spectral test, ACM Transactions on Modeling and Computer Simulation (TOMACS), v.9 n.1, p.31-44, Jan. 1999
	Meir Barel, Fast hardware random number generator for the Tausworthe sequence, Proceedings of the 16th annual symposium on Simulation, p.121-135, March 18-20, 1983, Tampa, Florida, United States
	W. J. Hemmerle, Generating pseudorandom numbers on a two's complement machine such as the IBM 360, Communications of the ACM, v.12 n.7, p.382-383, July 1969
	Munetaka Sakamoto , Susumu Morito, Combination of multiplicative congruential random-number generators with safe prime modulus, Proceedings of the 27th conference on Winter simulation, p.309-315, December 03-06, 1995, Arlington, Virginia, United States
	Peter Hellekalek, Inversive pseudorandom number generators: concepts, results and links, Proceedings of the 27th conference on Winter simulation, p.255-262, December 03-06, 1995, Arlington, Virginia, United States
	Christiane Lemieux , Pierre L'Ecuyer, Quasi-random numbers and their applications: using lattice rules for variance reduction in simulation, Proceedings of the 32nd conference on Winter simulation, December 10-13, 2000, Orlando, Florida
	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
	D. Guinier, A fast uniform astronomical random number generator, ACM SIGSAC Review, v.7 n.1, p.1-12, Spring 1989
	P. Hellekalek, Don't trust parallel Monte Carlo!, ACM SIGSIM Simulation Digest, v.28 n.1, p.82-89, July 1998
	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
	P. L'Ecuyer, Efficient and portable combined random number generators, Communications of the ACM, v.31 n.6, p.742-751, June 1988
	Samuel Gorenstein, Testing a random number generator, Communications of the ACM, v.10 n.2, p.111-118, Feb. 1967
	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
	John RB Whittlesey, Letters to the editor: on the multidimensional uniformity of pseudorandom generators, Communications of the ACM, v.12 n.5, p.247, May 1969
	P. D. Hortensius , R. D. McLeod , H. C. Card, Parallel Random Number Generation for VLSI Systems Using Cellular Automata, IEEE Transactions on Computers, v.38 n.10, p.1466-1473, October 1989
	Derick Wood, A few more trouble spots in ALGOL 60, Communications of the ACM, v.12 n.5, p.247-248, May 1969
	Aaldert Compagner, Fast and reliable random-number generation, Proceedings of the 24th conference on Winter simulation, p.438-442, December 13-16, 1992, Arlington, Virginia, United States
	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
	Kevin M. Finnigin , Barry E. Mullins , Richard A. Raines , Henry B. Potoczny, Cryptanalysis of an elliptic curve cryptosystem for wireless sensor networks, International Journal of Security and Networks, v.2 n.3/4, p.260-271, April 2007
	Hui-Chin Tang, Symmetry properties of multiple recursive random number generators in full period and spectral test, Applied Mathematics and Computation, v.142 n.2-3, p.291-303, 10 October 2003
	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
	John RB Whittlesey, A comparison of the correlational behavior of random number generators for the IBM 360, Communications of the ACM, v.11 n.9, p.641-644, Sept. 1968
	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
	Herbert S. Bright , Richard L. Enison, Quasi-Random Number Sequences from a Long-Period TLP Generator with Remarks on Application to Cryptography, ACM Computing Surveys (CSUR), v.11 n.4, p.357-370, Dec. 1979
	Herbert S. Bright , Richard L. Enison, Cryptography using modular software elements, Proceedings of the June 7-10, 1976, national computer conference and exposition, June 07-10, 1976, New York, New York
	Martina F. Schollmeyer , William H. Tranter, Noise generators for the simulation of digital communication systems, Proceedings of the 24th annual symposium on Simulation, p.264-275, April 1991, New Orleans, Louisiana, United States