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 2^e) with A and s_O odd to produce a pseudo-random sequence of integers in the range 0 to 2^e-1. The authors 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 2^e) where n is such that xⁿ+x+1 is a primitive binary polynomial. The period is increased from 2^e-2 to (2ⁿ-1)2^e-1. The overhead is an extra addition and the inclusion of a circular buffer of length n.