REAMC Report-002 (2020)

---

Abstract

The Additive Congruential Random Number (ACORN) generator represents an approach to generating uniformly distributed pseudo-random numbers which is straightforward to implement for arbitrarily large order and modulus (where the modulus is a sufficiently large power of 2, typically up to 2¹²⁰); it has been demonstrated in previous papers to give rise to sequences with long period which, for the k-th order ACORN generator with modulus a power of 2, can be proven from theoretical considerations to approximate in a particular defined sense to the desired properties of uniformity in up to k dimensions.

Extensive empirical testing using standard test software has demonstrated the excellent statistical performance of the ACORN generators with appropriately chosen order and modulus, over a very wide range of initialisations. In this report we present results of comprehensive testing, using the standard TestU01 package, for ACORN generators having modulus equal to 2¹²⁰, for all orders between 8 and 25 and a selection of larger values up to 101, and for a wide range of seed values. The main objective in this report has been to explore whether there are particular choices of seed for which the statistical performance of the resulting ACORN sequences fall below the levels that can generally be expected. The results presented in this report have identified a relatively small number of very specific seed values that need to be avoided. Some specific seeds to be avoided include very small values (close to 1) or very large seed values (such that 2 ¹²⁰ minus the seed is close to 1); also, certain values such that the seed divided by the modulus closely approximates a rational fraction of the form a / n where n is an odd integer and a is an integer less than n. Given that there are 2 ¹¹⁹ different possible choices of odd seed, it is not computationally feasible to test all the possible choices of seed or to enumerate all the seed values that should be avoided. However, based on the results of these tests, we are able to make a very powerful conjecture (which will be proposed, discussed and tested in part 2 of this report [1]) concerning the likelihood of an ACORN generator with order at least 8, modulus 2 ¹²⁰ and a randomly chosen seed value passing all the TestU01 BigCrush tests - which turns out to be an almost certain event.

Download full report