Concept - ACORN random numbers

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

Mathematical definition

Let the order k and the modulus M (typically an integer power of 2) be finite strictly positive integers, and let Y⁰₀ be a strictly positive integer satisfying 0 < Y⁰₀ < M.
Let   Y^m₀   m = 1, ..., k   be an arbitrary set of positive integer initial values each satisfying 0 ≤ Y^m₀ < M .

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

• Y⁰_n = Y⁰_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 X^k_n defined on [0,M) and [0,1) respectively, are the ACORN sequences of pseudo-random numbers.

ACORN intialisation

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 k dimensions, provided a few simple constraints on the initial parameter values are satisfied:

• 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⁰₀ 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)

ACORN algorithm

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³⁰ 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⁶⁰ (for general application) or M = 2¹²⁰ (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