ACORN (random number generator)

This article has multiple issues. Please help improve it or discuss these issues on the talk page. (Learn how and when to remove these messages) This article needs to be updated. Please help update this article to reflect recent events or newly available information. (April 2022) A major contributor to this article appears to have a close connection with its subject. It may require cleanup to comply with Wikipedia's content policies, particularly neutral point of view. Please discuss further on the talk page. See our advice if the article is about you and read our scam warning in case someone asks for money to edit this article. (April 2022) (Learn how and when to remove this message) (Learn how and when to remove this message)

The ACORN or ″Additive Congruential Random Number″ generators are a robust family of pseudorandom number generators (PRNGs) for sequences of uniformly distributed pseudo-random numbers, introduced in 1989 and still valid in 2019, thirty years later.

The additive congruential random number (ACORN) generator is a family of pseudorandom number generators introduced by R. S. Wikramaratna. It generates a sequence of values in the interval [0, 1) using a recursive procedure based on modular addition. The method was originally described in the *Journal of Computational Physics* in 1989. Subsequent work showed that ACORN generators can be represented as a special case of multiple recursive generators. Implementations using integer arithmetic can produce reproducible sequences across different machines, subject to consistent parameter choices and arithmetic representation. Later theoretical and empirical work examined the convergence and multidimensional distribution properties of ACORN sequences and evaluated their statistical performance using the TestU01 test suite. The results depend on the generator's order, modulus and initialization parameters.

Benefits

The main advantages of ACORN are simplicity of concept and coding, speed of execution, long period length, and mathematically proven convergence.

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

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

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" 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, and shown to give better speed of execution and statistical performance than Linear Congruential Generators and Chebyshev Generators.

In 1992, further results were published, 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, the creator of ACORN stated it to be a special case of a Multiple Recursive Generator (and, therefore, of a Matrix Generator), and formally demonstrated it in his 2008 paper, together with the results of empirical Diehard tests and comparisons with the NAG LCG (Linear Congruential Generator). Later in 2009, Wikramaratna gave formal proof to theoretical convergence of ACORN to k-distributed for modulus M=2^m as m tends to infinity, together with empirical results supporting this, which showed that ACORN generators are able to pass all the tests in the standard TESTU01 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, 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.

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

More recently, ACORN was presented in April 2019 at a poster session at a conference on Numerical algorithms for high-performance computational science 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. 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.

Code example

The following example in Fortran77 was published by Wikramaratna in 2008:

      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

References