This identifies some potential benefits of using ACORN and provides guidance on choosing appropriate parameters.
There are four compelling reasons to use ACORN generators:
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.
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).
Passes all TestU01 tests. Results obtained in 2018 with the most recent version of TestU01 show that for k > 9 and M = 290 or 2120, the resulting ACORN sequences consistently pass all the TestU01 tests - see 2019 poster (references).
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.
Modulus. When working with 32-bit integers, it is convenient to choose M = 230t 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 2120 the period will exceed 2120. 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