This explains the ACORN concept which is extremely simple, and gives a rigorous mathematical definition.

Let the order *k* and the modulus *M* (typically an integer power of 2) be finite strictly positive integers,
and let *Y*^{0}_{0} be a strictly positive integer satisfying 0 < *Y*^{0}_{0} < *M*.

Let *Y*^{m}_{0} *m* = 1, ..., *k* be an arbitrary set of positive integer initial values each satisfying 0 ≤ *Y*^{m}_{0} < *M* .

Then the *k*-th order Additive Congruential Random Number (ACORN) generator is defined by the equations

*Y*^{0}_{n}=*Y*^{0}_{n-1}*n*≥ 1 (1)*Y*= [^{m}_{n}*Y*^{m-1}_{n}+*Y*^{m}_{n-1}]_{modM}*n*≥ 1,*m*= 1, ... ,*k*(2)

where by [*Y*]_{mod M}we mean the remainder on dividing*Y*by*M**X*^{k}_{n}*= Y*^{k}_{n }*/ M**n*≥ 1 (3)

The sequences *Y ^{k}_{n}* and

It turns out that the numbers *X ^{k}_{n}* defined by
equations (1) - (3) approximate to being uniformly distributed on the unit
interval in up to

- the modulus
*M*needs to be a large integer (typically a prime power, with powers of 2 offering the most straightforward implementation) - the seed
*Y*^{0}_{0}and the modulus should be chosen to be relatively prime (two numbers are said to be relatively prime if they have no prime factors in common, which means that their greatest common divisor is 1; for*M*a power of two this requires only that the seed take an odd value)

The ACORN algorithm is very simple to implement in any high-level computer language.

Easiest
is to implement with *M* a large power of 2.

When using 32-bit integer arithmetic

*M*= 2^{30 }is easiest, but turns out not to be large enough in practice.*M =*2^{30s}(for any integer*s*) is a straightforward generalisation, avoiding arithmetic overflow by using*s*32-bit integers to represent each integer modulo*M=*2^{30s}.

With 64-bit integer arithmetic, larger *M* becomes feasible.

*s*64-bit integers used to represent an integer modulo 2^{60s}.- on 64 bit hardware, use of 64-bit integers allows speed up by a factor of 2 compared with the use of 32-bit integers.

In practice we recommend using *k* > 10, *M* = 2^{60} (for general application) or *M* = 2^{120} (for demanding applications requiring high-quality pseudo-random numbers that will consistently pass all the tests in standard test packages such as TestU01) and choose any odd value less than *M* for the seed.

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-03-31