More Web Proxy on the site http://driver.im/

article

Free access

Efficient and portable combined random number generators

Author:

P. L'EcuyerAuthors Info & Claims

Communications of the ACM, Volume 31, Issue 6

Pages 742 - 751

https://doi.org/10.1145/62959.62969

Published: 01 June 1988 Publication History

Abstract

In this paper we present an efficient way to combine two or more Multiplicative Linear Congruential Generators (MLCGs) and propose several new generators. The individual MLCGs, making up the proposed combined generators, satisfy stringent theoretical criteria for the quality of the sequence they produce (based on the Spectral Test) and are easy to implement in a portable way. The proposed simple combination method is new and produces a generator whose period is the least common multiple of the individual periods. Each proposed generator has been submitted to a comprehensive battery of statistical tests. We also describe portable implementations, using 16-bit or 32-bit integer arithmetic. The proposed generators have most of the beneficial properties of MLCGs. For example, each generator can be split into many independent generators and it is easy to skip a long subsequence of numbers without doing the work of generating them all.

References

[1]

Borosh, S., and Niederreiter, H. Optimal multipliers for pseudorandom number generation by the linear congruential method. BIT 23 (1983), 65-74.

[2]

Bratley, P., Fox, B.L., and Schrage, L.E. A Guide to Simulation. Springer-Verlag, New York, N.Y., 2nd ed., 1987.

Digital Library

[3]

Clark., R.N. A Pseudorandom Number Generator. Simulation 45, 5 (Nov. 1985), 252-255.

[4]

Coveyou, R.R., and MacPherson, R.D. Fourier analysis of uniform random number generators. J. ACM 14 (Jan. 1967), 100-119.

Digital Library

[5]

Dieter, U. How to calculate shortest vectors in a lattice. Math. Cornput. 29 (July 1975), 827-833.

[6]

Dudewicz, E.J., Karian, Z.A., and Marshall, R.}., III. Random number generation on microcomputers. Modeling and Simulation on Microcomputers: 1985, The Society for Computer Simulation, 1985, pp. 9-14.

[7]

Figie}, K.D., and Sule, D.R. New lagged product test for random number generators. Comput. Ind. Eng. 9, 3 (Mar. 1985), 287-296.

[8]

Fishman, G.S., and Moore, L.S., Ill. A statistical evaluation of multiplicative congruential random number generators with modulus 23'-1. J. Am. Star. Assoc. 77 (Mar. 1982), 129-136.

[9]

Fishman, G.S., and Moore, L.S., III. An exhaustive anai{ysis of multiplicative congruential random number generators with modulus 23~ - 1. SIAM J. Sci. Stat. Comput. 7, 1 (Jan. 1986), 24-45.

Digital Library

[10]

Fushimi, M., and Tezuka, S. The k-distribution of generalized feedback shift register pseudorandom numbers. Commun. ACM 26, 7 (July 1983), 516-523.

Digital Library

[11]

Knuth, D.E. The Art of Computer Programming--Seminumerical Algorithms, vol. 2, 2nd ed., Addison-Wesley, Reading, Mass. 1981.

Digital Library

[12]

Lewis, P.A.W., Goodman, A.S., and Miller, ).M. A pseudo-random number generator for the system/360. IBM Syst. J. 8, 2 (1969), 136- 146.

Digital Library

[13]

Marsaglia, G. Random numbers fall mainly in the planes. Proc. Nat. Acad. Sci. 61 (Sept. 1968), 25-28.

[14]

Marse, K. and Roberts, S.D. Implementing a portable FORTRAN uniform {0, 1) generator. Simulation 41, 4 {Oct. 1983}, 135-139.

[15]

Modianos, D.T., Scott, R.C., and Cornwell, L.W. Random number generation on microcomputers. Interfaces 14, 2 (Mar.-April 1984), 81-87.

Digital Library

[16]

Nance, R.E., and Overstreet, C., Jr. Some experimental observations on the behavior of composite random number generators. Oper. Res. 26, 5 (Sept.-Oct. 1978), 915-935.

[17]

Niederreiter, H. Quasi-Monte Carlo methods and pseudo-random numbers. Bull. Amer. Math. Soc. 84, 6 (Nov. 1978), 957-1041.

[18]

Payne, W.H., Rabung, J.R., and Bogyo, T.P. Coding the Lehmer pseudo-random number generator. Commun. ACM 12,; (Feb. 1969), 85-86.

Digital Library

[19]

Schrage, L. A more portable Fortran random number generator. ACM Trans. Math. Soft. 5, 2 (June 1979), 132-138.

Digital Library

[20]

Thesen, A. An efficient generator of uniformly distributed random variates between zero and one. Simulation 44, 1 I tan. 1985), 17-22.

[21]

Wichmann, B.A and Hill, I.D. An efficient and portable pseudorandom number generator. Appl. Stat. 31 (1982), 188-190.

Cited By

Hu S(2025)Shell sort with expected complexity of O(nlog2n)Theoretical Computer Science10.1016/j.tcs.2025.1151221034(115122)Online publication date: Apr-2025
https://doi.org/10.1016/j.tcs.2025.115122
Kang SKim GHur UKim J(2024)Forensic Analysis of wxSQLite3-Encrypted Databases and Its ApplicationElectronics10.3390/electronics1307132513:7(1325)Online publication date: 1-Apr-2024
https://doi.org/10.3390/electronics13071325
Nandi S(2024)On the Mandelbrot set of perturbed cubic complex polynomialsResearch in Mathematics10.1080/27684830.2024.239229911:1Online publication date: 23-Aug-2024
https://doi.org/10.1080/27684830.2024.2392299
Show More Cited By

Recommendations

Bit-Wise Behavior of Random Number Generators

In 1985, G. Marsaglia proposed the m-tuple test, a runs test on bits, as a test of nonrandomness of a sequence of pseudorandom integers. We try this test on the outputs from a large set of pseudorandom number generators and discuss the behavior of the ...
Resolution-stationary random number generators

Besides speed and period length, the quality of uniform random number generators (RNGs) is usually assessed by measuring the uniformity of their point sets, formed by taking vectors of successive output values over their entire period length. For F"2-...
Efficient, perfect random number generators
CRYPTO '88: Proceedings on Advances in cryptology

We describe a method that transforms every perfect random number generator into one that can be accelerated by parallel evaluation. Our method of parallelization is perfect, m parallel processors speed the generation of pseudo-random bits by a factor m; ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Communications of the ACM

Communications of the ACM Volume 31, Issue 6

June 1988

149 pages

ISSN:0001-0782

EISSN:1557-7317

DOI:10.1145/62959

Editor:
P. J. Denning
NASA Ames Research Center, Moffett Field, CA

Issue’s Table of Contents

Copyright © 1988 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 June 1988

Published in CACM Volume 31, Issue 6

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

381
Total Citations
View Citations
3,399
Total Downloads

Downloads (Last 12 months)460
Downloads (Last 6 weeks)92

Reflects downloads up to 05 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

Hu S(2025)Shell sort with expected complexity of O(nlog2n)Theoretical Computer Science10.1016/j.tcs.2025.1151221034(115122)Online publication date: Apr-2025
https://doi.org/10.1016/j.tcs.2025.115122
Kang SKim GHur UKim J(2024)Forensic Analysis of wxSQLite3-Encrypted Databases and Its ApplicationElectronics10.3390/electronics1307132513:7(1325)Online publication date: 1-Apr-2024
https://doi.org/10.3390/electronics13071325
Nandi S(2024)On the Mandelbrot set of perturbed cubic complex polynomialsResearch in Mathematics10.1080/27684830.2024.239229911:1Online publication date: 23-Aug-2024
https://doi.org/10.1080/27684830.2024.2392299
Deng LWinter BShiau JLu HKumar NYang C(2023)Parallelizable efficient large order multiple recursive generatorsParallel Computing10.1016/j.parco.2023.103036117(103036)Online publication date: Sep-2023
https://doi.org/10.1016/j.parco.2023.103036
Dunn WShultis J(2023)Pseudorandom Number GeneratorsExploring Monte Carlo Methods10.1016/B978-0-12-819739-4.00011-1(55-110)Online publication date: 2023
https://doi.org/10.1016/B978-0-12-819739-4.00011-1
Almaraz Luengo E(2022)A brief and understandable guide to pseudo-random number generators and specific models for securityStatistics Surveys10.1214/22-SS13616:noneOnline publication date: 1-Jan-2022
https://doi.org/10.1214/22-SS136
Sei YOhsuga A(2022)False Event Message Detection Robust to Burst Attacks in Wireless Sensor NetworksIEEE Open Journal of the Communications Society10.1109/OJCOMS.2022.32080883(1630-1642)Online publication date: 2022
https://doi.org/10.1109/OJCOMS.2022.3208088
Williams BCarlson AHiromoto R(2022)Novel Innovations that Failed to Improve Weak PRNGs2022 13th International Conference on Computing Communication and Networking Technologies (ICCCNT)10.1109/ICCCNT54827.2022.9984517(1-6)Online publication date: 3-Oct-2022
https://doi.org/10.1109/ICCCNT54827.2022.9984517
Bhattacharjee KDas S(2022)A search for good pseudo-random number generatorsComputer Science Review10.1016/j.cosrev.2022.10047145:COnline publication date: 1-Aug-2022
https://dl.acm.org/doi/10.1016/j.cosrev.2022.100471
(2022)BibliographyStatistical Mechanics10.1016/B978-0-08-102692-2.00027-2(711-725)Online publication date: 2022
https://doi.org/10.1016/B978-0-08-102692-2.00027-2
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

Figures

Tables

Media

View Issue’s Table of Contents