Critique - ACORN random numbers

This identifies some potential benefits of using ACORN and provides guidance on choosing appropriate parameters.

BENEFITS

There are four compelling reasons to use ACORN generators:

• extremely light-weight and easy code (a few lines) giving reproducible results in any high-level language and on any platform;
• theoretical convergence is mathematically proven;
• all current empirical test suites for PRNGs are passed;
• can be easily extended to give sequences with longer period length, and improved statistical performance over higher dimensions and with higher precision.

Easy. A few tens of lines of code suffice to implement ACORN - for FORTRAN77 and javascript code examples and executables, see the download page.

Fast. Speed comparisons are always fraught with difficulty, since they vary with different hardware, languages, compilers.
We believe that the computational performance of ACORN generator is comparable to other commonly-used methods that also pass all the TestU01 tests.
We observe that in general the overall execution time of programs that make use of pseudo random numbers is likely to be dominated by other computations rather than by the time required for the generation of the pseudo-random numbers. 
In addition:

• We note that with the ACORN generator speed improvements are possible by taking advantage of 64-bit integer arithmatic on 64-bit hardware (in Fortran, a factor of about 2 improvement compared with 32-bit arithmetic on the same hardware).
• Further speed increases can be obtained by careful implementation of the modular arithmetic that is required in implementation of the ACORN generator (in Fortran, a factor of about 5 improvement is possible compared with the standard implementation).
• Should 128-bit (or even 256-bit) hardware become commonplace in the future, the ACORN algorithm is well-suited to take take maximum advantage of those developments.
  

Mathematically proven convergence to unform k-dimensional distribution. It has been proved that a k-th order ACORN sequence approximates to uniformity in k-dimensions in a sense that has been defined in the 2009 paper (references page).

• As far as we know, this convergence result is unique to the ACORN generator.

Passes all TestU01 tests. Results obtained in 2018 with the most recent version of TestU01 show that for k > 9 and M = 2⁹⁰ or 2¹²⁰, the resulting ACORN sequences consistently pass all the TestU01 tests - see 2019 poster (references).

PARAMETERS

The three key parameters that govern the statistical behaviour are the order k, modulus M, seed (a strictly positive integer, less than M) and k initial values (each can be a positive integer or zero, less than M), which uniquely define and ACORN sequence. Therefore for the same given values of these parameters, any correctly implemented ACORN generator will give rise to an identical sequence (to within the rounding error that arises in converting an integer modulo M to a real number, defined on the unit interval, by dividing the integer by M) on any hardware, and using any computing language.

Order. A k-th order ACORN sequence approximates to uniformity in up to k-dimensions (provided the modulus and the seed are chosen appropriately).

The standard TestU01 test suite carries out tests of uniformity in up to about 8 dimensions.

• It has been demonstrated by Wikramaratna, 2019 that an ACORN generator with order between 9 and 20 and modulus   2¹²⁰   will reliably pass all the TestU01 tests provided the seed is chosen to be odd - see references, 2019 poster.
• On the other hand, any ACORN generator of order k<8 will certainly fail on one or more of the TestU01 tests, simply because ACORN will only approximate to uniformity in at most k dimensions.
• It is recommended that an order k of between 9 and 20 is selected for general use. Note that execution time is approximately proportional to k so there is some benefit in limiting the value of k to what is required. If your application needs uniformity in higher dimensions then larger values of k may be appropriate.

Modulus. When working with 32-bit integers, it is convenient to choose M = 2^30t for some appropriate integer t. The ACORN algorithm then uses t 32-bit integers to represent an integer modulo M.

Empirical testing using TestU01 has demonstrated that the statistical performance of the resulting sequences improves with increasing t. On the other hand, choosing t = 4 or t = 3 seems to be sufficient to pass the tests in the TestU01 test suite. Choosing t = 2 still passes the majority of the tests in TestU01, but occasional failures on certain tests begin to occur. Choosing t = 1 is clearly inadequate from a statistical perspective.

Note that execution time is approximately proportional to t so there is some benefit in limiting the value of t to what is required.

Seed. The only constraint on the choice of seed is that it should be relatively prime with the modulus M. If the modulus is a power of 2, then the seed can be assigned any odd value to satisfy this condition. There are M/2 such choices of seed, and each one gives a completely different sequence with the same period and similar statistical properties.

It is straightforward to demonstrate that if M is a power of 2 and if the seed is odd then the period length of the resulting ACORN sequence will exceed M (in fact, it will be a known multiple of M) for any value of k.

Thus, if the modulus is 2¹²⁰ the period will exceed 2¹²⁰. We believe that this is more than enough for any conceivable practical application today. We would be very pleased to hear of or discover an application which required longer-period sequences.

All information on this site © 2019 Roy Wikramaratna.
You may use all information for research and teaching purposes (with due acknowledgement).
For business or commercial or other use for gain, see contact page.
created 2019-01-31 / updated 2019-04-05