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 Y00 be a strictly positive integer satisfying 0 < Y00 < M.
Let   Ym0   m = 1, ..., k   be an arbitrary set of positive integer initial values each satisfying 0 ≤ Ym0 < M .

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

The sequences Ykn and Xkn defined on [0,M) and [0,1) respectively, are the ACORN sequences of pseudo-random numbers.

ACORN intialisation

It turns out that the numbers Xkn 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:

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

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

In practice we recommend using k > 10, M = 260 (for general application) or M = 2120 (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