Simple but effective modification to a multiplicative congruential random-number generator
A popular form of random-number generator uses the recurrence sk = (ASk−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 sk = (Ask−1 + Sk−n mod 2e where n is such that xn + 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.
