Algorithm 806: SPRNG: a scalable library for pseudorandom number generation
Open accessAbstract
In this article we present background, rationale, and a description of the Scalable Parallel Random Number Generators (SPRNG) library. We begin by presenting some methods for parallel pseudorandom number generation. We will focus on methods based on parameterization, meaning that we will not consider splitting methods such as the leap-frog or blocking methods. We describe, in detail, parameterized versions of the following pseudorandom number generators: (i) linear congruential generators, (ii) shift-register generators, and (iii) lagged-Fibonacci generators. We briefly describe the methods, detail some advantages and disadvantages of each method, and recount results from number theory that impact our understanding of their quality in parallel applications. SPRNG was designed around the uniform implementation of different families of parameterized random number generators. We then present a short description of SPRNG. The description contained within this document is meant only to outline the rationale behind and the capabilities of SPRNG. Much more information, including examples and detailed documentation aimed at helping users with putting and using SPRNG on scalable systems is available at htt;//sprng.sc.fsu.edu. In this description of SPRNG we discuss the random-number generator library as well as the suite of tests of randomness that is an integral part of SPRNG. Random-number tools for parallel Monte Carlo applications must be subjected to classical as well as new types of empirical tests of randomness to eliminate generators that show defects when used in scalable envionments.
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Integrity signals
Registry
Cites
Statistics
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Claims other papers make about this one
Each is checked against this paper’s own text: does it say what the citing paper says it does?
Parallel random bit generation methods could dramatically improve the generation rate and scalability by producing many random bits simultaneously.
“Parallel random bit generation methods could dramatically improve the generation rate and scalability by producing many random bits simultaneously.”
From Scalable parallel physical random number generator based on a superluminescent LED (2011) · cites this paper as [10]
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Cites
The Art of Computer Programming
Knuth, D. E. (1968) · Cited by 16,097 · see citing works
Mersenne twister: a 623-dimensionally equidistributed uniform pseudo-random number generator
Matsumoto, M., & Nishimura, T. (1998) · ACM Transactions on Modeling and Computer Simulation · doi:10.1145/272991.272995 · Cited by 5,780 · see citing works
The Art of Computer Programming. Volume 2: Seminumerical Algorithms.
Taussky, O., & Knuth, D. E. (1970) · American Mathematical Monthly · doi:10.2307/2317055 · Cited by 3,863 · see citing works
Random Number Generation and Quasi-Monte Carlo Methods.
Collings, B. J., & Niederreiter, H. (1993) · Journal of the American Statistical Association · doi:10.2307/2290359 · Cited by 2,944 · see citing works
Uniform distribution of sequences
Kuipers, L., & Niederreiter, H. (1974) · CERN Document Server (European Organization for Nuclear Research) · Cited by 2,400 · see citing works
Condor-a hunter of idle workstations
Litzkow, M., Livny, M., & Mutka, M. W. (2003) · doi:10.1109/dcs.1988.12507 · Cited by 2,257 · see citing works
Shift-register synthesis and BCH decoding
Massey, J. (1969) · IEEE Transactions on Information Theory · doi:10.1109/tit.1969.1054260 · Cited by 2,205 · see citing works
Golomb, S. W. (2014) · WORLD SCIENTIFIC eBooks · doi:10.1142/9361 · Cited by 2,194 · see citing works
Introduction to Finite Fields and their Applications
Lidl, R., & Niederreiter, H. (1994) · Cambridge University Press eBooks · doi:10.1017/cbo9781139172769 · Cited by 2,098 · see citing works
Random number generators: good ones are hard to find
Park, S. K., & Miller, K. (1988) · Communications of the ACM · doi:10.1145/63039.63042 · Cited by 1,268 · see citing works
Fortuna, E., Gianni, P., & Trager, B. (1961) · American Mathematical Monthly · doi:10.2307/2311524 · Cited by 875 · see citing works
RANDOM NUMBERS FALL MAINLY IN THE PLANES
Marsaglia, G. (1968) · Proceedings of the National Academy of Sciences · doi:10.1073/pnas.61.1.25 · Cited by 530 · see citing works
Equations over Finite Fields An Elementary Approach
Schmidt, W. M. (1976) · Lecture notes in mathematics · doi:10.1007/bfb0080437 · Cited by 528 · see citing works
Applications of Number Theory to Numerical Analysis
(1972) · Elsevier eBooks · doi:10.1016/c2013-0-11736-9 · Cited by 506 · see citing works
Low-discrepancy and low-dispersion sequences
Niederreiter, H. (1988) · Journal of Number Theory · doi:10.1016/0022-314x(88)90025-x · Cited by 491 · see citing works
Mathematical Methods in Large-scale Computing Units
Lehmer, D. H. (1951) · Cited by 446 · see citing works
Monte Carlo simulations: Hidden errors from ‘‘good’’ random number generators
Ferrenberg, A. M., Landau, D. P., & Wong, Y. J. (1992) · Physical Review Letters · doi:10.1103/physrevlett.69.3382 · Cited by 437 · see citing works
Random numbers generated by linear recurrence modulo two
Tausworthe, R. C. (1965) · Mathematics of Computation · doi:10.1090/s0025-5718-1965-0184406-1 · Cited by 432 · see citing works
Generalized Feedback Shift Register Pseudorandom Number Algorithm
Lewis, T., & Payne, W. H. (1973) · Journal of the ACM · doi:10.1145/321765.321777 · Cited by 314 · see citing works
L’Ecuyer, P. (1990) · Communications of the ACM · doi:10.1145/84537.84555 · Cited by 279 · see citing works
Uniform random number generation
L’Ecuyer, P. (1994) · Annals of Operations Research · doi:10.1007/bf02136827 · Cited by 268 · see citing works
Uniform Random Numbers: Theory and Practice
Tezuka, S. (1995) · Cited by 246 · see citing works
(2008) · Springer eBooks · doi:10.1007/978-0-387-32833-1_341 · Cited by 207 · see citing works
Tezuka, S. (1995) · Springer eBooks · doi:10.1007/978-1-4615-2317-8 · Cited by 197 · see citing works
Exact Distribution of Energies in the Two-Dimensional Ising Model
Beale, P. D. (1996) · Physical Review Letters · doi:10.1103/physrevlett.76.78 · Cited by 191 · see citing works
Matsumoto, M., & Kurita, Y. (1992) · ACM Transactions on Modeling and Computer Simulation · doi:10.1145/146382.146383 · Cited by 190 · see citing works
The Structure of Linear Congruential Sequences
Marsaglia, G. (1972) · Elsevier eBooks · doi:10.1016/b978-0-12-775950-0.50013-3 · Cited by 168 · see citing works
A non-linear congruential pseudo random number generator
Eichenauer, J., & Lehn, J. (1986) · Statistische Hefte · doi:10.1007/bf02932576 · Cited by 157 · see citing works
Implementing a random number package with splitting facilities
L’Ecuyer, P., & Côté, S. (1991) · ACM Transactions on Mathematical Software · doi:10.1145/103147.103158 · Cited by 141 · see citing works
Matrices and the structure of random number sequences
Marsaglia, G., & Tsay, L.-H. (1985) · Linear Algebra and its Applications · doi:10.1016/0024-3795(85)90192-2 · Cited by 118 · see citing works
Physical Tests for Random Numbers in Simulations
Vattulainen, I., Ala-Nissilä, T., & Kankaala, K. (1994) · Physical Review Letters · doi:10.1103/physrevlett.73.2513 · Cited by 110 · see citing works
ANALYSIS OF RANDOM NUMBER GENERATORS USING MONTE CARLO SIMULATION
Coddington, P. D. (1994) · International Journal of Modern Physics C · doi:10.1142/s0129183194000726 · Cited by 99 · see citing works
Testing parallel random number generators
Srinivasan, A., Mascagni, M., & Ceperley, D. M. (2003) · Parallel Computing · doi:10.1016/s0167-8191(02)00163-1 · Cited by 98 · see citing works
Self-citationRandom Number Generators for Parallel Computers
Coddington, P. D. (1997) · Syracuse University Libraries (Syracuse University) · Cited by 96 · see citing works
Parallelization of random number generators and long-range correlations
Matteis, A. D., & Pagnutti, S. (1988) · Numerische Mathematik · doi:10.1007/bf01397554 · Cited by 81 · see citing works
On correlations in “good” random number generators
Grassberger, P. (1993) · Physics Letters A · doi:10.1016/0375-9601(93)91122-l · Cited by 65 · see citing works
Random number generators for MIMD parallel processors
Percus, O. E., & Kalos, M. H. (1989) · Journal of Parallel and Distributed Computing · doi:10.1016/0743-7315(89)90002-6 · Cited by 62 · see citing works
Computing 𝜋(𝑥): the Meissel-Lehmer method
Lagarias, J. C., Miller, V. S., & Odlyzko, A. M. (1985) · Mathematics of Computation · doi:10.1090/s0025-5718-1985-0777285-5 · Cited by 55 · see citing works
Pseudo-random trees in Monte Carlo
Frederickson, P. O., Hiromoto, R. E., Jordan, T. L., et al. (1984) · Parallel Computing · doi:10.1016/s0167-8191(84)90072-3 · Cited by 52 · see citing works
On the Periods of Generalized Fibonacci Recurrences
Brent, R. P. (1994) · Mathematics of Computation · doi:10.2307/2153583 · Cited by 52 · see citing works
Bad subsequences of well-known linear congruential pseudorandom number generators
Entacher, K. (1998) · ACM Transactions on Modeling and Computer Simulation · doi:10.1145/272991.273009 · Cited by 51 · see citing works
Uniform Random Number Generators for Supercomputers
Brent, R. P. (1992) · ANU Open Research (Australian National University) · Cited by 51 · see citing works
Analysis of spectral projectors in one-dimensional domains
Maday, Y. (1990) · Mathematics of Computation · doi:10.1090/s0025-5718-1990-1035939-1 · Cited by 49 · see citing works
Long-range correlations in linear and non-linear random number generators
Matteis, A. D., & Pagnutti, S. (1990) · Parallel Computing · doi:10.1016/0167-8191(90)90108-l · Cited by 49 · see citing works
A Fast, High Quality, and Reproducible Parallel Lagged-Fibonacci Pseudorandom Number Generator
Mascagni, M., Cuccaro, S. A., Pryor, D. V., et al. (1995) · Journal of Computational Physics · doi:10.1006/jcph.1995.1130 · Cited by 43 · see citing works
Self-citationRandom Number Generators for Parallel Applications
Srinivasan, A., Ceperley, D. M., & Mascagni, M. (1999) · Advances in chemical physics · doi:10.1002/9780470141649.ch2 · Cited by 42 · see citing works
Self-citationComputing 𝜋(𝑥): the Meissel, Lehmer, Lagarias, Miller, Odlyzko method
Deléglise, M., & Rivat, J. (1996) · Mathematics of Computation · doi:10.1090/s0025-5718-96-00674-6 · Cited by 40 · see citing works
TESTS OF RANDOM NUMBER GENERATORS USING ISING MODEL SIMULATIONS
Coddington, P. D. (1996) · International Journal of Modern Physics C · doi:10.1142/s0129183196000235 · Cited by 38 · see citing works
On a new class of pseudorandom numbers for simulation methods
Niederreiter, H. (1994) · Journal of Computational and Applied Mathematics · doi:10.1016/0377-0427(94)90385-9 · Cited by 37 · see citing works
Parallel linear congruential generators with prime moduli
Mascagni, M. (1998) · Parallel Computing · doi:10.1016/s0167-8191(98)00010-6 · Cited by 35 · see citing works
Self-citationOn a nonlinear congruential pseudorandom number generator
Kato, T., Wu, L.-M., & Yanagihara, N. (1996) · Mathematics of Computation · doi:10.1090/s0025-5718-96-00694-1 · Cited by 34 · see citing works
Controlling correlations in parallel Monte Carlo
Matteis, A. D., & Pagnutti, S. (1995) · Parallel Computing · doi:10.1016/0167-8191(94)00073-j · Cited by 34 · see citing works
A class of parallel random number generators
Matteis, A. D., & Pagnutti, S. (1990) · Parallel Computing · doi:10.1016/0167-8191(90)90146-z · Cited by 33 · see citing works
Uniform random number generators for parallel computers
Deák, I. (1990) · Parallel Computing · doi:10.1016/0167-8191(90)90039-c · Cited by 28 · see citing works
Lagged-Fibonacci random number generators on parallel computers
Makino, J. (1994) · Parallel Computing · doi:10.1016/0167-8191(94)90042-6 · Cited by 22 · see citing works
Cluster-flipping Monte Carlo algorithm and correlations in good' random number generators
Selke, W., Talapov, A. L., & Shchur, L. N. (1993) · Cited by 20 · see citing works
Some Methods of Parallel Pseudorandom Number Generation
Mascagni, M. (1999) · The IMA volumes in mathematics and its applications · doi:10.1007/978-1-4612-1516-5_12 · Cited by 19 · see citing works
Self-citationTechniques for Testing the Quality of Parallel Pseudorandom Number Generators.
Cuccaro, S. A., Mascagni, M., & Pryor, D. V. (1995) · Cited by 16 · see citing works
Self-citationFramework for testing random numbers in parallel calculations
Vattulainen, I. (1999) · Physical review. E, Statistical physics, plasmas, fluids, and related interdisciplinary topics · doi:10.1103/physreve.59.7200 · Cited by 15 · see citing works
Parallel Pseudorandom Number Generation Using Additive Lagged-Fibonacci Recursions
Mascagni, M., Robinson, M. L., Pryor, D. V., et al. (1995) · Lecture notes in statistics · doi:10.1007/978-1-4612-2552-2_17 · Cited by 13 · see citing works
Self-citationDeléglise, M., & Rivat, J. (1998) · Mathematics of Computation · doi:10.1090/s0025-5718-98-00977-6 · Cited by 5 · see citing works
Serial and Parallel Random Number Generation
Mascagni, M. (1999) · Springer eBooks · doi:10.1007/978-94-011-4792-7_16 · Cited by 4 · see citing works
Self-citation
Flagged first, then by citations
Research works printed but not linked: 4
- MARSAGLIA, G. 1985. A current view of random number generators. In Computing Science and Statistics: Proceedings of the XVIth Symposium on the Interface. 3-10.
- MASCAGNI, M. 1997. A parallel non-linear Fibonacci pseudorandom number generator. In Proceedings of SIAM's 45th Anniversary Meeting (Stanford, CA, July 14 -18). SIAM, Philadelphia, PA. Abstract
- PRYOR, D. V., CUCCARO, S. A., MASCAGNI, M., AND ROBINSON, M. L. 1994. Implementation of a portable and reproducible parallel pseudorandom number generator. In Proceedings of the Conference on Supercomputing '94 (Washington, DC, Nov. 14 -18), G. M. Johnson, Chair. IEEE Computer Society Press, Los Alamitos, CA, 311-319.
- ZHOU, M. AND MASCAGNI, M. 1999. Parallel Monte Carlo in a distributed environment: SPRNG and condor. In Proceedings of the 1st Southern Symposium on Computing. Received: November 1998; revised: September 1999 and May 2000; accepted: May 2000
Cited by
Sorted by citations
Parallel random numbers: as easy as 1, 2, 3
Salmon, J. K., Moraes, M. A., Dror, R. O., & Shaw, D. E. (2011) · Proceedings of 2011 International Conference for High Performance Computing, Networking, Storage and Analysis · doi:10.1145/2063384.2063405 · Cited by 227 · see citing works
Scalable parallel physical random number generator based on a superluminescent LED
Li, X., Cohen, A. B., Murphy, T. E., & Roy, R. (2011) · Optics Letters · doi:10.1364/ol.36.001020 · Cited by 146 · see citing works
- Authors
- Mascagni, M., & Srinivasan, A.
- Affiliations
- Florida State University (US)
- Indian Institute of Technology Bombay (IN)
- Venue
- ACM Transactions on Mathematical Software
- Published
- 2000-09
- Volume
- 26
- Issue
- 3
- Pages
- 436-461
- ISSN
- 0098-3500 (ISSN-L)
- 1557-7295
- OpenAlex
- W2086611351
- Cited by
- 275
- References
- 62
- Citations by year
- 2026: 6 · 2025: 4 · 2024: 2 · 2023: 8 · 2022: 5 · 2021: 10 · 2020: 6 · 2019: 11 · 2018: 2 · 2017: 15 · 2016: 15 · 2015: 17 · 2014: 12 · 2013: 13 · 2012: 14
- FWCI
- 9.12
- Type
- journal article
- Language
- en
- Open access
- bronze
- doi.org
- Locations
- ACM Transactions on Mathematical Software (publishedVersion)
- Funders
- Sandia National Laboratories
- Topics
- Physical Sciences › Mathematics › Numerical Analysis › Mathematical Approximation and Integration
- Social Sciences › Decision Sciences › Management Science and Operations Research › Simulation Techniques and Applications
- Physical Sciences › Computer Science › Hardware and Architecture › Parallel Computing and Optimization Techniques
- Keywords
- linear congruential generator, lagged Fibonacci generator, scalable systems
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
