ACORN - A new method for generating sequences of uniformly distributed pseudo-random numbers (Q1123528)

This paper presents a new family of pseudo-random number generators called the ACORN (additive congruential random number) generators. The kth order ACORN generator \(X^ k_ j\) is defined recursively from a seed \(X^ 0_ 0\) \((0<X^ 0_ 0<1)\) and a set of k initial values \(X^ m_ 0\), \((m=1,...,k)\) each satisfying \(0\leq X^ m_ 0<1\) by \(X^ 0_ n=X^ 0_{n-1}\), (n\(\geq 1)\), \(X^ m_ n=(X_ n^{m- 1}+X^ m_{n-1})_{mod M}\), (n\(\geq 1\), \(m=1,...,k)\), and is distributed uniformly in the interval [0,M). Theorems on the period length for the ACORN generators are derived. Some empirical tests of randomness indicate that the performance of the ACORN generators for \(k\geq 5\) is superior to the Chebyshev generators, while being compatible to the multiplicative congruential generators. The execution time on IBM PC-XT for the ACORN generators is considerably faster than for the linear congruential ones, while the period lengths are longer even for relatively small k. It is concluded that the ACORN generator is of particular values in applications when both period length and execution times become significant factors.