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

article

Free access

Parallel streams of linear random numbers in the spectral test

Editor: David M. Nicol Author:

Karl EntacherAuthors Info & Claims

ACM Transactions on Modeling and Computer Simulation (TOMACS), Volume 9, Issue 1

Pages 31 - 44

https://doi.org/10.1145/301677.301682

Published: 01 January 1999 Publication History

Abstract

This paper reports analyses of subsequences of linear congruential pseudorandom numbers by means of the spectral test. Such subsequences occur in particular simulation setups or as methods to obtain parallel streams of pseudorandom numbers for parallel and distributed simulation. Especially in the latter case, two kinds of substreams are of special interest: lagged random numbers with step sizes k, and consecutive streams of random numbers of length l. We show how to analyze correlations within and between lagged subsequences with arbitrary step sizes k. Analyzing consecutive streams with the spectral test is related to the well-known long-range correlation analysis of linear congruential generators. Whereas the latter was carried out to show correlations between pairs of processors only, the spectral test provides a convenient method to study correlations between larger numbers of parallel streams as well.

References

[1]

ANDERSON, S. L. 1990. Random number generations generators on vector supercomputers and other advanced architectures. SIAM Rev. 32, 2 (June 1990), 221-251.

[2]

CEPERLEY, D., MASCAGNI, M., AND SRINIVASAN, A. 1997. SPRNG: Scalable parallel random number generators. University of Illinois at Urbana-Champaign, Champaign, IL. http:// www.ncsa.uiuc.edu/Apps/SPRNG/

[3]

COVEYOU, R. AND MACPHERSON, R. 1967. Fourier analysis of uniform random number generators. J. ACM 14, 100-119.

[4]

DE MATTEIS, A., EICHENAUER-HERRMANN, J., AND GROTHE, H. 1992. Computation of critical distances within multiplicative congruential pseudorandom number sequences. J. Comput. Appl. Math. 39, 1 (Feb.), 49-55.

[5]

DE MATTEIS, A. AND PAGNUTTI, S. 1988. Parallelization of random number generators and long-range correlations. Numer. Math. 53, 5 (Aug. 1988), 595-608.

[6]

DEMATTEIS, A. AND PAGNUTTI, S. 1990. A class of parallel random number generators. Parallel Comput. 13, 193-198.

[7]

DEMATTEIS, A. AND PAGNUTTI, S. 1992. Critical distances in pseudorandom sequences generated with composite moduli. Int. J. Comput. Math. 43, 189-196.

[8]

DE MATTEIS, A. AND PAGNUTTI, S. 1995. Controlling correlations in parallel Monte Carlo. Parallel Comput. 21, 1 (Jan. 1995), 73-84.

[9]

DIETER, U. 1975. How to calculate shortest vectors in a lattice. Math. Comput. 29, 131, 827-833.

[10]

DURST, M.J. 1989. Using linear congruential generators for parallel random number generation. In Proceedings of the Winter Conference on Simulation (WSC '89, Washington, D.C., Dec. 4-6, 1989), E. A. MacNair, K. J. Musselman, and P. Heidelberger, Eds. ACM Press, New York, NY, 462-466.

[11]

EICHENAUER-HERRMANN, J. AND GROTHE, H. 1989. A remark on long-range correlations in multiplicative congruential pseudo random number generators. Numer. Math. 56, 6 (Dec. 1989), 609-611.

[12]

EICHENAUER-HERRMANN, J., HERRMANN, E., AND WEGENKITTL, S. 1998. A survey of quadratic and inversive congruential pseudorandom numbers. In Lecture Notes in Statistics. Springer-Verlag, New York, NY, 66-97.

[13]

ENTACHER, K. 1998. Bad subsequences of well-known linear congruential pseudorandom number generators. ACM Trans. Model. Comput. Simul. 7, 1, 61-70.

[14]

ENTACHER, K. 1998. A collection of selected pseudorandom number generators with linear structures -- updated version. Tech. Rep. Dept. of Mathematics, University of Salzburg, Austria. http://random.mat.sbg, ac. at/

[15]

ENTACHER, K., UHL, A., AND WEGENKITTL, S. 1998. Linear and inversive pseudorandom numbers for parallel and distributed simulation. In Proceedings of the Twelfth Workshop on Parallel and Distributed Simulation (PADS'98, Banff, Alberta, Canada, May 26th - 29th). IEEE Computer Society Press, Los Alamitos, CA, 90-97.

[16]

FISHMAN, G. 1996. Monte Carlo: Concepts, algorithms, and applications. In Operations Research. Springer Series on Operations Research, vol. 1. Springer-Verlag, New York, NY.

[17]

HELLEKALEK, P. 1995. Inversive pseudorandom number generators: Concepts, results and links. In Proceedings of the 1995 Winter Simulation Conference (WSC '95, Arlington, VA, Dec. 3-6), W. R. Lilegdon, D. Goldsman, C. Alexopoulos, and K. Kang, Eds. ACM Press, New York, NY, 255-262.

[18]

HELLEKALEK, P. 1998a. On correlation analysis of pseudorandom numbers. In Lecture Notes in Statistics. Springer-Verlag, New York, NY, 251-265.

[19]

HELLEKALEK, P. 1998b. On the assessment of random and quasi-random point sets. In Random and Quasi-Random Point Sets. P. Hellekalek and G. Larcher, Eds. Lecture Notes in Statistics. Springer-Verlag, New York, NY.

[20]

HELLEKALEK, P., ENTACHER, K., LEEB, H., LENDL, O., AND WEGENKITTL, S. 1995. The pLab www-server. Available at: http://random.mat.sbg.ac.at+. Also accessible via ftp. University of Salzburg, Austria.

[21]

KNUTH, D. 1973. The Art of Computer Programming. Addison-Wesley, Reading, MA.

[22]

LAW, A. AND KELTON, W. 1991. Simulation Modeling and Analysis (2 ed.). McGraw-Hill, Inc., New York, NY.

[23]

L'ECUYER, P. 1997. Bad lattice structures for vectors of non-successive values produced by some linear recurrences. INFORMS J. Comput. 9, 57-60.

[24]

L'ECUYER, P. 1998. Random number generation. In Handbook of Simulation, J. Banks, Ed. John Wiley & Sons, Inc., New York, NY.

[25]

L'ECUYER, P. 1999. Tables of linear congruential generators of different sizes and good lattice structure. Math. Comput. 68, 225, 249-260.

[26]

L'ECUYER, P. AND ANDRES, T. 1997. A random number generator based on the combination of four LCGs. Math. Comput. Simul. 44, 99-107.

[27]

L'ECUYER, P. AND COUTURE, R. 1997. An implementation of the lattice and spectral tests for multiple recursive linear random number generators. INFORMS J. Comput. 9, 2, 206-217.

[28]

MASCAGNI, M. 1998. Parallel linear congruential generators with prime moduli. Parallel Comput. 24, 5-6, 923-936.

[29]

MASUDA, N. AND ZIMMERMANN, F. 1996. PRNGlib: A parallel random number generator library. Tech. Rep. http://www.cscs.ch/Official/Publications.html.

[30]

NIEDERREITER, H. 1992. Random Number Generation and Quasi-Monte Carlo Methods. CBMS-NSF regional conference series in applied mathematics. SIAM, Philadelphia, PA.

[31]

NIEDERREITER, H. 1995. New developments in uniform pseudorandom number and vector generation. In Monte Carlo and Quasi Monte Carlo Methods in Scientific Computing, H. Niederreiter and P. J.-S. Shiue, Eds. Springer-Verlag, New York, NY.

[32]

PERCUS, O. E. AND KALOS, M. H. 1989. Random number generators for MIMD parallel processors. J. Parallel Distrib. Comput. 6, 3 (June), 477-497.

[33]

RIPLEY, B. 1983. The lattice structure of pseudo-random number generators. Phil. Trans. Roy. Soc. London Ser. A 389, 197-204.

Cited By

Steele GVigna S(2021)Computationally easy, spectrally good multipliers for congruential pseudorandom number generatorsSoftware: Practice and Experience10.1002/spe.303052:2(443-458)Online publication date: 29-Sep-2021
https://doi.org/10.1002/spe.3030
Smed JHakonen H(2017)BibliographyAlgorithms and Networking for Computer Games10.1002/9781119259770.biblio(357-373)Online publication date: 19-Jun-2017
https://doi.org/10.1002/9781119259770.biblio
Entacher K(2016)On the CRAY-System Random Number GeneratorSIMULATION10.1177/00375497990720030872:3(163-169)Online publication date: 18-Aug-2016
https://doi.org/10.1177/003754979907200308
Show More Cited By

Index Terms

Parallel streams of linear random numbers in the spectral test
1. Computing methodologies
  1. Modeling and simulation
2. Mathematics of computing
  1. Probability and statistics
    1. Probabilistic reasoning algorithms
      1. Random number generation

Recommendations

Bad subsequences of well-known linear congruential pseudorandom number generators
Special issue on uniform random number generation

We present a spectral test analysis of full-period subsequences with small step sizes generated by well-known linear congruential pseudorandom number generators. Subsequences may occur in certain simulation problems or as a method to get parallel ...
On the lattice structure of the add-with-carry and subtract-with-borrow random number generators

Marsaglia and Zaman recently proposed new classes of random number generators, called add-with-carry(AWC) and subtract-with-borrow(SWB), which are capable of quickly generating very long-period (pseudo)-random number sequences using very little memory. ...
An Implementation of the Lattice and Spectral Tests for Multiple Recursive Linear Random Number Generators

<P>We discuss the implementation of theoretical tests to assess the structural properties of simple or combined linear congruential and multiple recursive random number generators. In particular, we describe a package implementing the so-called spectral ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Transactions on Modeling and Computer Simulation

ACM Transactions on Modeling and Computer Simulation Volume 9, Issue 1

Jan. 1999

80 pages

ISSN:1049-3301

EISSN:1558-1195

DOI:10.1145/301677

Editor:
David M. Nicol
Dartmouth College, Hanover, NH

Issue’s Table of Contents

Copyright © 1999 ACM.

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 January 1999

Published in TOMACS Volume 9, Issue 1

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

7
Total Citations
View Citations
491
Total Downloads

Downloads (Last 12 months)35
Downloads (Last 6 weeks)11

Reflects downloads up to 30 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Steele GVigna S(2021)Computationally easy, spectrally good multipliers for congruential pseudorandom number generatorsSoftware: Practice and Experience10.1002/spe.303052:2(443-458)Online publication date: 29-Sep-2021
https://doi.org/10.1002/spe.3030
Smed JHakonen H(2017)BibliographyAlgorithms and Networking for Computer Games10.1002/9781119259770.biblio(357-373)Online publication date: 19-Jun-2017
https://doi.org/10.1002/9781119259770.biblio
Entacher K(2016)On the CRAY-System Random Number GeneratorSIMULATION10.1177/00375497990720030872:3(163-169)Online publication date: 18-Aug-2016
https://doi.org/10.1177/003754979907200308
Alhakim AAkinwande M(2009)A multiple stream generator based on de Bruijn digraph homomorphismsJournal of Statistical Computation and Simulation10.1080/0094965080232212979:11(1371-1380)Online publication date: Nov-2009
https://doi.org/10.1080/00949650802322129
Entacher KSchell TUhl A(2005)Bad Lattice PointsComputing10.1007/s00607-004-0105-z75:4(281-295)Online publication date: 1-Aug-2005
https://dl.acm.org/doi/10.1007/s00607-004-0105-z
Entacher KSchell TSchmid WUhl A(2003)Defects in parallel Monte Carlo and quasi-Monte Carlo integration using the leap-frog techniqueParallel Algorithms and Applications10.1080/106371903100008802118:1-2(13-26)Online publication date: May-2003
https://doi.org/10.1080/1063719031000088021
Entacher KSchell TUhl A(2001)Optimization of random number generators: efficient search for high-quality LCGsProbabilistic Engineering Mechanics10.1016/S0266-8920(01)00021-216:4(289-293)Online publication date: Oct-2001
https://doi.org/10.1016/S0266-8920(01)00021-2

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

Media

Figures

Other

Tables

View Issue’s Table of Contents