The ACORN or ″Additive Congruential Random Number″ generators are a robust family of PRNGs for sequences of uniformly distributedpseudo-random numbers, introduced in 1989 and still valid in 2019, thirty years later. Introduced by R.S.Wikramaratna, ACORN was originally designed for use in geostatistical and geophysicalMonte Carlo simulations, and later extended for use on parallel computers. Over the ensuing decades, theoretical analysis, empirical testing, and practical application work have continued, despite the appearance and promotion of other better-known PRNGs.
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 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. 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 and should not be confused with it - ACG appears to have been used for a variant of the LCG described by Knuth.
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, ACORN was stated to be a special case of a Multiple Recursive Generator, and this was formally demonstrated in 2008 in a paper which also published results of empirical Diehard tests and comparisons with the NAG LCG. In 2009, formal proof was given of theoretical convergence of ACORN to k-distributed for modulus M=2m 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. Since 2009 ACORN has been included in the NAG 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 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.
Code example
The following example in Fortran77 was published in 2008 which includes a discussion of how to initialise : DOUBLE PRECISION FUNCTION ACORNJ C Fortran implementation of ACORN random number generator C of order less than or equal to 120 and C modulus less than or equal to 2^60. 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. IMPLICIT DOUBLE PRECISION PARAMETER COMMON /IACO2/ KORDEJ,MAXJNT,IXV1,IXV2 DO 7 I=1,KORDEJ IXV1=+IXV1) IXV2=+IXV2) IF THEN IXV2=IXV2-MAXJNT IXV1=IXV1+1 ENDIF IF IXV1=IXV1-MAXJNT 7 CONTINUE ACORNJ=/MAXJNT RETURN END
