Hostname: page-component-586b7cd67f-tf8b9 Total loading time: 0 Render date: 2024-11-22T06:30:56.087Z Has data issue: false hasContentIssue false
  • English
  • Français

Evaluation of splittable pseudo-random generators*

Part of: JFP Research Articles

Published online by Cambridge University Press:  17 June 2015

HANS GEORG SCHAATHUN
HANS GEORG SCHAATHUN*
Affiliation:
Aalesund University College, Pb. 1517, N-6025 Ålesund, Norway (e-mail: [email protected])
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

Pseudo-random number generation is a fundamental problem in computer programming. In the case of sequential processing the problem is very well researched, but parallel processing raises new problems whereof far too little is currently understood. Splittable pseudo-random generators (S-PRNG) have been proposed to meet the challenges of parallelism. While applicable to any programming paradigm, they are designed to be particularly suitable for pure functional programming. In this paper, we review and evaluate known constructions of such generators, and we identify flaws in several large classes of generators, including Lehmer trees, the implementation in Haskell's standard library, leapfrog, and subsequencing (substreaming).

Type
Articles
Information
Journal of Functional Programming , Volume 25 , 2015 , e6
Copyright
Copyright © Cambridge University Press 2015 

Footnotes

*

The research was partially funded by Regionalt Forskingsfond Midt-Norge through the project Dynamic Resource Allocation with Maritime Application (DRAMA), grant no. ES504913.

References

Brown, R. G. (2015 January) Dieharder: A Random Number Test Suite. Software. Available from http://www.phy.duke.edu/~rgb/General/dieharder.php.Google Scholar
Burton, F. W. & Page, R. L. (1992) Distributed random number generation. J. Funct. Program. 2 (2), 203–212.CrossRefGoogle Scholar
Bye, R. T. & Schaathun, H. G. (2014) An improved receding horizon genetic algorithm for the tug fleet optimisation problem. In Proceedings of the 28th European Conference on Modelling and Simulation (ECMS 2014). ECMS European Council for Modelling and Simulation, pp. 682–690.CrossRefGoogle Scholar
Carta, D. G. (1990) Two fast implementations of the minimal standard random number generator. Commun. ACM 33 (1), 87–88.CrossRefGoogle Scholar
Claessen, K. & Pałka, M. H. (2013a) Splittable pseudorandom number generators using cryptographic hashing. In Proceedings of the 2013 ACM SIGPLAN Symposium on Haskell. Haskell'13. New York, NY, USA: ACM, pp. 47–58.CrossRefGoogle Scholar
Claessen, K. & Pałka, M. H. (2013b) The tf-Random Package. Accessed 2015-01-15. Online at: https://hackage.haskell.org/package/tf-random.Google Scholar
Cuccaro, S. A., Mascagni, M., & Pryor, D. V. (1995) Techniques for testing the quality of parallel pseudorandom number generators. In Proceedings of the 7th SIAM Conference on Parallel Processing for Scientific Computing, Bailey, D. H., Bjørstad, P. E., Gilbert, J. R., Mascagni, M., Schreiber, R. S., Simon, H. D., Torczon, V. J., & Watson, L.T. (eds), SIAM, pp. 279–284.Google Scholar
De Matteis, A. & Pagnutti, S. (1990) Long-range correlations in linear and non-linear random number generators. Parallel Comput. 14 (2), 207–210.CrossRefGoogle Scholar
Eddy, W. F. (1990) Random number generators for parallel processors. J. Comput. Appl. Math., 31 (1), 63–71.CrossRefGoogle Scholar
Frederickson, P., Hiromoto, R., Jordan, T. L., Smith, B. & Warnock, T. (1984) Pseudo-random trees in Monte Carlo. Parallel Comput. 1 (2), 175–180.CrossRefGoogle Scholar
Hackage. (2011) The Random Package. Haskell Random Number Library. Documentation. Accessed 2015-01-16. Online at: http://hackage.haskell.org/package/random-1.1.Google Scholar
Halton, J. H. (1989) Pseudo-random trees: Multiple independent sequence generators for parallel and branching computations. J. Comput. Phys. 84 (1), 1–56.CrossRefGoogle Scholar
Klamkin, M. S. & Newman, D. J. (1967) Extensions of the birthday surprise. J. Comb. Theory 3 (3), 279–282.CrossRefGoogle Scholar
Knuth, D. E. (1998) The Art of Computer Programming, vol. 2: Seminumerical Algorithms, 3rd ed., Addison-Wesley.Google Scholar
Koniges, A. E. & Leith, C. E. (1989) Parallel processing of random number generation for Monte Carlo turbulence simulation. J. Comput. Phys. 81 (1), 230–235.CrossRefGoogle Scholar
Krawczyk, H. (1992) How to predict congruential generators. J. Algorithms 13 (4), 527–545.CrossRefGoogle Scholar
L'Ecuyer, P. (1988) Efficient and portable combined random number generators. Commun. ACM 31 (6), 742–749 and 774.CrossRefGoogle Scholar
L'Ecuyer, P. (2012) Random number generation. In Handbook of Computational Statistics: Concepts and Methods, Gentle, J. E., Härdle, W. K. & Mori, Y. (eds), 2nd ed., Springer, pp. 35–71.CrossRefGoogle Scholar
L'Ecuyer, P. & Simard, R. (2007) TestU01: A C library for empirical testing of random number generators. ACM Trans. Math. Softw. 33 (4), Article no. 22.CrossRefGoogle Scholar
L'Ecuyer, P., Simard, R., Chen, E. J. & Kelton, W. D. (2002) An objected-oriented random-number package with many long streams and substreams. Oper. Res. 50 (6), 1073–1075.CrossRefGoogle Scholar
Leiserson, C. E., Schardl, T. B. & Sukha, J. (2012) Deterministic parallel random-number generation for dynamic-multithreading platforms. ACM SIGPLAN Not. 47 (8), 193–204.CrossRefGoogle Scholar
Marlow, S. (2013) Parallel and Concurrent Programming in Haskell. O'Reilly.Google Scholar
Marsaglia, G. (1968) Random numbers fall mainly in the planes. Proc.Natl. Acad. Sci. United States Am. 61 (1), 25–28.CrossRefGoogle ScholarPubMed
Mascagni, M. (1998) Parallel linear congruential generators with prime moduli. Parallel Comput. 24 (5–6), 923–936.CrossRefGoogle Scholar
Matsumoto, M. & Nishimura, T. (1998) Dynamic creation of pseudorandom number generators. In Monte Carlo and quasi-Monte Carlo Methods, 1998: Proceedings of a Conference Held at the Claremont Graduate University, June 22–26, Niederreiter, H. & Spanier, J. (eds), Claremont, CA, USA: Springer, pp. 56–69.Google Scholar
Matsumoto, M., Wada, I., Kuramoto, A. & Ashihara, H. (2007) Common defects in initialization of pseudorandom number generators. ACM Trans. Model. Comput. Simul. 17 (4), Article no. 15.CrossRefGoogle Scholar
Menezes, A. J., van Oorschot, P. C. & Vanstone, S. A. (1997) Handbook of Applied Cryptography. CRC Press.Google Scholar
O'Sullivan, B., Goerzen, J. & Stewart, D. (2008) Real World Haskell. O'Reilly.Google Scholar
Park, S. K. & Miller, K. W. (1988) Random number generators: Good ones are hard to find. Commun. ACM 31 (10), 1192–1201.CrossRefGoogle Scholar
Percus, Ora E. & Kalos, M. H. (1989) Random number generators for MIMD parallel processors. J. Parallel Distrib. Comput. 6 (3), 477–497.CrossRefGoogle Scholar
Salmon, J. K., Moraes, M. A., Dror, R. O. & Shaw, D. E. (2011) Parallel random numbers: As easy as 1, 2, 3. In High performance computing, networking, storage and analysis (SC11), 2011 International conference for. ACM, pp. 1–12.CrossRefGoogle Scholar
Schaathun, H. G. (2014) Parallell slump (Om å parallellisera genetiske algoritmar i Haskell) Norsk informatikkonferanse. Open access at: http://ojs.bibsys.no/index.php/NIK/index. ISSN 1892-0721.Google Scholar
Steele, Guy L. Jr., Lea, D. & Flood, C. H. (2014) Fast splittable pseudorandom number generators. ACM SIGPLAN Not. 49 (10), 453–472.CrossRefGoogle Scholar
Warnock, T. T. (1983) Synchronization of random number generators. Congressus Numerantium 37, 135–144.Google Scholar
Wu, P.-C. & Huang, K.-C. (2006) Parallel use of multiplicative congruential random number generators. Comput. Phys. Commun. 175 (1), 25–29.CrossRefGoogle Scholar
Submit a response

Discussions

No Discussions have been published for this article.