“ACORN (PRNG)”的意思、由来-开放百科全书

ACORN or ″Additive Congruential Random Number″ generators are a robust family of PRNGs (pseudorandom number generators) for sequences of uniformly distributed pseudo-random numbers.

Introduced in 1989 by R.S.Wikramaratna,^[1] the ACORN generator was originally designed for use in geostatistical and geophysical Monte Carlo simulations, and later extended for use on parallel computers.^[2]

Over the ensuing decades, theoretical analysis (formal proof of convergence and statistical results), empirical testing (using standard test suites), and practical application work have continued, despite the appearance and promotion of other better-known [but not necessarily better performing] PRNGs.

Benefits

The main advantages of ACORN are simplicity of concept and coding, speed of execution, and long period length.^[3]

ACORN is particularly simple to implement in exact integer arithmetic, in various computer languages, using only a few lines of code.^[4]

Integer arithmetic is preferred to the real arithmetic modulo 1 in the original presentation, as the algorithm is then reproducible, producing exactly the same sequence on any machine and in any language,^[2] and its periodicity is mathematically provable.

The ACORN generator has not seen the wide adoption of some other PRNGs, although it is included in the Fortran and C library routines of NAG Numerical Library.^[6] Various reasons have been put forward for this.^[5] Nevertheless, theoretical and empirical research is ongoing to further justify the continuing use of ACORN as a robust and effective PRNG.

Provisos

In testing, ACORN performs extremely well, for appropriate parameters.^[5] However in its present form, ACORN has not been shown to be suitable for cryptography.{{citation needed|date=February 2019}}

There have been few critical appraisals regarding ACORN. One of these,^[6] warns of an unsatisfactory configuration of the acorni() routine when using GSLIB GeoStatistical modelling and simulation library,^[7] and proposes a simple solution for this issue. Essentially the modulus parameter should be increased in order to avoid this issue.^[8] ^[5]

Another brief reference to ACORN simply states that the "... ACORN generator proposed recently […] is in fact equivalent to a MLCG with matrix A such that a~ = 1 for i 2 j, aq = 0 otherwise" ^[9] but does not take the analysis further.

History and development

Initially, ACORN was implemented in real arithmetic in FORTRAN77,^[1] and shown to give better speed of execution and statistical performance than Linear Congruential Generators and Chebyshev Generators.

In 1992, further results were published,^[10] implementing the ACORN Pseudo-Random Number Generator in exact integer arithmetic which ensures reproducibility across different platforms and languages, and stating that for arbitrary real-precision arithmetic it is possible to prove convergence of the ACORN sequence to k-distributed as the precision increases.

In 2000, ACORN was stated to be a special case of a Multiple Recursive Generator (and, therefore, of a Matrix Generator),^[2] and this was formally demonstrated in 2008 ^[17] in a paper which also published results of empirical Diehard tests and comparisons with the NAG LCG (Linear Congruential Generator).

In 2009, formal proofwas given ^[4] of theoretical convergence of ACORN to k-distributed for modulus M=2^m as m tends to infinity (as previously alluded to in 1992 ^[10]) , together with empirical results supporting this, which showed that ACORN generators are able to pass all the tests in the standard TESTU01 ^[11] suite for testing of PRNGs (when appropriate order and modulus parameters are selected).

Since 2009 ACORN has been included in the NAG (Numerical Algorithms Group) FORTRAN and C library routines,^[12]^[13] together with other well-known PRNG routines. This implementation of ACORN works for arbitrarily large modulus and order, and is available for researchers to download.^[13]

ACORN was also implemented in GSLIB GeoStatistical modelling and simulation library.^[7]

Code example

The following example in Fortran77 was published in 2008 ^[14] which includes a discussion of how to initialise :

External links

The ACORN website (ACORN.wikramaratna.org) contains information regarding the ACORN concept and algorithm, its author, a complete list of references, and information about current research directions.

References

1. ^¹Wikramaratna, R.S. (1989). ACORN — A new method for generating sequences of uniformly distributed Pseudo-random Numbers. Journal of Computational Physics. 83. 16-31.
2. ^¹²R.S. Wikramaratna, Pseudo-random number generation for parallel processing — A splitting approach, SIAM News 33 (9) (2000).
3. ^{{Cite web|url=http://acorn.wikramaratna.org/concept.html|title=ACORN concept and algorithm|website=acorn.wikramaratna.org/concept.html}}
4. ^¹R.S. Wikramaratna, Theoretical and empirical convergence results for additive congruential random number generators, Journal of Computational and Applied Mathematics (2009), doi:10.1016/j.cam.2009.10.015
5. ^¹²{{Cite web|url=http://acorn.wikramaratna.org/critique.html|title=ACORN initialisation and critique|website=acorn.wikramaratna.org/critique.html}}
6. ^Ortiz, Julián & V. Deutsch, Clayton. (2014). Random Number Generation with acorni: A Warning Note.
7. ^¹GsLib An open-source package dedicated to geostatistics, source code in Fortran 77 and 90.
8. ^{{Cite web|url=http://acorn.wikramaratna.org/references.html|title=ACORN references and links|website=acorn.wikramaratna.org/references.html}}
9. ^L’Ecuyer, Pierre. (1990). Random Numbers for Simulation.. Commun. ACM. 33. 85-97. 10.1145/84537.84555.
10. ^¹R.S. Wikramaratna, Theoretical background for the ACORN random number generator, Report AEA-APS-0244, AEA Technology, Winfrith, Dorset, UK, 1992.
11. ^P. L'Ecuyer, R. Simard, TestU01: A C library for empirical testing of random number generators, ACM Trans. on Math. Software 33 (4) (2007) Article 22.
12. ^NAG, Numerical Algorithms Group (NAG) Fortran Library Mark 22, Numerical Algorithms Group Ltd., Oxford, UK, 2009.
13. ^¹²{{Cite web|url=https://www.nag.co.uk/numeric/cl/nagdoc_cl26/html/g05/g05intro.html|title=g05 Chapter Introduction : NAG Library, Mark 26|website=www.nag.co.uk}}
14. ^¹{{Cite journal|last=Wikramaratna|first=Roy|date=2008|title=The additive congruential random number generator – a special case of a multiple recursive generator|url=|journal=J. Comput. Appl. Math.|volume=216|pages=371–387|doi=10.1016/j.cam.2007.05.018|via=}}