R S Wikramaratna
November 2022
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 2120); 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.
This report investigates the mathematical relationship between the ACORN generators and Pascal’s triangle. It turns out that if the (k+1)-th diagonal of Pascal’s triangle is considered modulo a large integer M, then it is equivalent to a k-th order ACORN sequence with seed equal to 1 and initial values all zero; normalising this sequence to the unit interval (by dividing each term in the sequence by the modulus M) leads to a sequence that approximates to being uniformly distributed on the unit interval. The report goes on to demonstrate an augmented form of Pascal’s triangle that can be shown to encapsulate all the possible ACORN generators.
Demonstration of this new relationship, between the ACORN generators and Pascal’s triangle, does not lead to any significant algorithmic developments in terms of generating ACORN sequences (this is due to the inherent speed and efficiency of the existing ACORN algorithm). Having said this, Pascal’s triangle has been shown over the years to possess many interesting and diverse mathematical properties, and the present work has established the existence of some novel and previously unknown mathematical properties associated both with Pascal’s triangle itself and with certain generalisations thereof.
Download full report