A fast uniform astronomical random number generator

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

A fast uniform astronomical random number generator

Full text

Pdf (575 KB)

Source

ACM SIGSAC Review archive
Volume 7 , Issue 1 (Spring 1989) table of contents

Pages: 1 - 12

Year of Publication: 1989

ISSN:0277-920X

Author

D. Guinier

Publisher

ACM New York, NY, USA

Bibliometrics

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

Additional Information:

abstract references cited by index terms

Tools and Actions:	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/70951.70952 What is a DOI?

ABSTRACT

The present method generates machine-independent uniform random sequences of real numbers in the interval (0.,1.) excluding 1. It uses a set of up to 1024 independent multiplicative congruential generators working with:• modulii which are chosen prime numbers whose values have been fixed according to the positive 31-bit positive integer arithmetic available and in the form of 2.P'+1, where P's are also primes.• multipliers which are selected from one of their corresponding primitive elements as multipliers to achieve each full cycle independently.The "astronomical" maximum periodicity can be considered as infinite: O (10⁶⁰²¹); it can be adjusted if required by the user in the sequential version RAN01 or statistically reaching the maximum in the improved "stagger" version DAN01.An "acceptable" composite period is estimated to be O (10¹⁸⁹) for a set of only 32 of such independent generators: this fact could find a nice application in the realization of efficient hash-functions in smart cards.An implementation in structured FORTRAN 77 shows very good results in terms of statistical proprieties, velocity and periodicity.

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	<b>Beasley J. D., Springer S. G.</b> (1977): Algorithm AS111: The Percentage Points of the Normal Distribution. Appl Stat, Vol. 26, pp. 118--121.
	2	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 [doi>10.1145/356789.356795]
	3	<b>Carmichael R. D.</b> (1910): Bull Amer Math Soc, Vol. 16, pp. 232--238.
	4	R. R. Coveyou , R. D. Macpherson, Fourier Analysis of Uniform Random Number Generators, Journal of the ACM (JACM), v.14 n.1, p.100-119, Jan. 1967 [doi>10.1145/321371.321379]
	5	<b>Grafton R. G. T.</b> (1981): Algorithm AS 157: The runs-up and runs-down tests. Appl Stat, Vol. 30, pp. 81--85.
	6	Daniel Guinier, Random numbers for stochastic simulation, ACM SIGBIO Newsletter, v.6 n.4, March 1984 [doi>10.1145/992237.992242]
	7	<b>Guinier D.</b> (1984b): HASDAN: An original universal "Bursting Hash-Coding" Function permitting all ASCII Codes, Independent of the character Sources and insensitive to the Aggregates with an expected Low Rate number of Collisions. DECUS, Mini-Tasker, RT11 SIG, Vol. 10, No. 1, 1-1984, pp. 7--13.
	8	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 [doi>10.1145/62179.62184]
	9	Richard W. Hamming, Coding and information theory (2nd ed.), Prentice-Hall, Inc., Upper Saddle River, NJ, 1986
	10	<b>Jansson B.</b> (1966): Random Number Generators. Victor Pettersons Bokindustri Aktiebolag, Stockholm, pp. 1--205.
	11	<b>Kendall M. G., Badington-Smith B.</b> (1946): Tables of random sampling numbers: Tracts for Computers No.24, Cambridge Univ Press.
	12	Donald E. Knuth, The art of computer programming, volume 2 (3rd ed.): seminumerical algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1997
	13	J. B. Kruskal, Extremely portable random number generator, Communications of the ACM, v.12 n.2, p.93-94, Feb. 1969 [doi>10.1145/362848.362865]
	14	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]
	15	<b>Lewis P. A. W., Goodman A. S., Miller J. M.</b> (1969): A pseudo-random number generator for the System/360. IBM Syst J, Vol. 8, No. 2, pp. 136--146.
	16	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]
	17	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]
	18	<b>Senne K. D.</b> (1974): Machine-Independent Monte-Carlo Evaluation of the Performance of Dynamic Stochastic Systems. J Stochastics, Vol. 1, pp. 215--238.
	19	Claude E. Shannon , Warren Weaver, A Mathematical Theory of Communication, University of Illinois Press, Champaign, IL, 1963
	20	Adi Shamir, On the Generation of Cryptographically Strong Pseudo-Random Sequences, Proceedings of the 8th Colloquium on Automata, Languages and Programming, p.544-550, July 13-17, 1981
	21	<b>Wichmann B. A., Hill I. D.</b> (1982a): A pseudo-random number generator. NPL Report DITC 6/82, pp. 1--30.
	22	<b>Wichmann B. A., Hill I. D.</b> (1982b): Algorithm AS 183: An efficient and Portable Pseudo-random Number Generator. Roy Stat Soc, pp. 188--190.

CITED BY 2

	Pierre L'Ecuyer, Random numbers for simulation, Communications of the ACM, v.33 n.10, p.85-97, Oct. 1990
	D. Guinier, Philosopher's corner, ACM SIGSAC Review, v.7 n.2, p.18-28, Summer 1989