ACORN (PRNG)

The 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 and still valid in 2019, thirty years later.

Introduced by R.S.Wikramaratna,[1] ACORN 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, long period length, and mathematically proven convergence.[3]

The algorithm can be extended, if future applications require “better quality” pseudo random numbers and longer period, by increasing the order and the modulus as required. In addition, recent research has shown that the ACORN generators pass all the tests in the TestU01 test suite, current version 1.2.3, with an appropriate choice of parameters and with a few very straightforward constraints on the choice of initialisation; it is worth noting, as pointed out by the authors of TestU01, that some widely-used pseudo-random number generators fail badly on some of the tests .

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.[5] Various reasons have been put forward for this.[6] 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.[6] However in its present form, ACORN has not been shown to be suitable for cryptography.

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

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"[10] but the analysis is not taken further.

ACORN is not the same as ACG (Additive Congruential Generator) and should not be confused with it - ACG appears to have been used for a variant of the LCG (Linear Congruential Generator) described by Knuth (1997).

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,[11] 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[12] in a paper which also published results of empirical Diehard tests and comparisons with the NAG LCG (Linear Congruential Generator).

In 2009, formal proof was given[4] of theoretical convergence of ACORN to k-distributed for modulus M=2m as m tends to infinity (as previously alluded to in 1992[11]) , together with empirical results supporting this, which showed that ACORN generators are able to pass all the tests in the standard TESTU01[13] 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,[14][5] 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.[5]

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

More recently, ACORN was presented in April 2019 at a poster session at a conference on Numerical algorithms for high-performance computational science[15] at the Royal Society in London, and in June 2019 at a Seminar of the Numerical Analysis Group at the Mathematical Institute of the University of Oxford.[16] where it was stated that statistical performance is better than some very widely used generators (including the Mersenne Twister MT19937) and comparable to the best currently available methods" and that ACORN generators have been shown to reliably pass all the tests in the TestU01, while some other generators including Mersenne Twister do not pass all these tests. The poster and the presentation can be found at.[9]

Code example

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

      DOUBLE PRECISION FUNCTION ACORNJ(XDUMMY)
C
C          Fortran implementation of ACORN random number generator
C          of order less than or equal to 120 (higher orders can be
C          obtained by increasing the parameter value MAXORD) and
C          modulus less than or equal to 2^60.
C
C          After appropriate initialization of the common block /IACO2/
C          each call to ACORNJ generates a single variate drawn from
C          a uniform distribution over the unit interval.
C
      IMPLICIT DOUBLE PRECISION (A-H,O-Z)
      PARAMETER (MAXORD=120,MAXOP1=MAXORD+1)
      COMMON /IACO2/ KORDEJ,MAXJNT,IXV1(MAXOP1),IXV2(MAXOP1)
      DO 7 I=1,KORDEJ
        IXV1(I+1)=(IXV1(I+1)+IXV1(I))
        IXV2(I+1)=(IXV2(I+1)+IXV2(I))
        IF (IXV2(I+1).GE.MAXJNT) THEN
          IXV2(I+1)=IXV2(I+1)-MAXJNT
          IXV1(I+1)=IXV1(I+1)+1
        ENDIF
      IF (IXV1(I+1).GE.MAXJNT) IXV1(I+1)=IXV1(I+1)-MAXJNT
    7 CONTINUE
      ACORNJ=(DBLE(IXV1(KORDEJ+1)) 
     1          +DBLE(IXV2(KORDEJ+1))/MAXJNT)/MAXJNT
      RETURN
      END

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. "ACORN concept and algorithm". 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. "g05 Chapter Introduction : NAG Library, Mark 26". www.nag.co.uk.
  6. "ACORN initialisation and critique". acorn.wikramaratna.org/critique.html.
  7. Ortiz, Julián & V. Deutsch, Clayton. (2014). Random Number Generation with acorni: A Warning Note.
  8. GsLib An open-source package dedicated to geostatistics, source code in Fortran 77 and 90.
  9. "ACORN references and links". acorn.wikramaratna.org/references.html.
  10. L’Ecuyer, Pierre. (1990). Random Numbers for Simulation.. Commun. ACM. 33. 85-97. 10.1145/84537.84555.
  11. R.S. Wikramaratna, Theoretical background for the ACORN random number generator, Report AEA-APS-0244, AEA Technology, Winfrith, Dorset, UK, 1992.
  12. Wikramaratna, Roy (2008). "The additive congruential random number generator – a special case of a multiple recursive generator". J. Comput. Appl. Math. 216: 371–387. doi:10.1016/j.cam.2007.05.018.
  13. 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.
  14. NAG, Numerical Algorithms Group (NAG) Fortran Library Mark 22, Numerical Algorithms Group Ltd., Oxford, UK, 2009.
  15. "Numerical algorithms for high-performance computational science". The Royal Society.
  16. "The Additive Congruential Random Number (ACORN) Generator - pseudo-random sequences that are well distributed in k-dimensions". Oxford University Mathematical Institute.
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.