SIMPLE BUT EFFECTIVE MODIFICATION TO A MULTIPLICATIVE CONGRUENTIAL RANDOM-NUMBER GENERATOR

A popular form of random-number generator uses the recurrence s(k) = (As(k-1) mod 2e) with A and S0 odd to produce a pseudo-random sequence of integers in the range 0 to 2e - 1. We give a simple modification which increases the guaranteed period by an enormous factor with only a small computational overhead. The recurrence is changed to S(k) = (AS(k-1) + S(k-n) mod 2e) where n is such that x(n) + x + 1 is a primitive binary polynomial. The period is increased from 2e-2 to (2n - 1)2e-1. The overhead is an extra addition and the inclusion of a circular buffer of length n.