5.4.2 Multiple-Recursive Generators
In practical Monte Carlo work, we use only a small subsequence of the numbers generated by a pseudorandom number generator. It might seem sufficient for the generator’s period to exceed the number of pseudorandom numbers used by only a few orders of magnitude, but this is not the case. In Section 5.5, we will see that it is desirable to employ pseudorandom number generators with extremely high periods, even for applications that use only a few pseudorandom numbers.
In theory, through judicious selection of the parameters η, a, and c, an LCG can be made to have a period of any order of magnitude. In the past, parameters were chosen so that
[5.15]
This ensured that all calculations performed by an LCG could, with suitable coding,15 be performed in floating-point form without rounding on 32-bit computers. This restriction limited the maximal period η that could be achieved with LCGs. Higher period LCGs could be implemented with multiple-precision arithmetic, but this was computationally inefficient. An alternative was to explore generalizations of LCGs that had high periods but could still be implemented with single-precision floating-point arithmetic on 32-bit computers. The most popular of these were multiple-recursive generators (MRGs) defined by
[5.16]
[5.17]
for some positive integer k, positive integers a1, a2, … , am, and seed values z[0], z[1], … , z[k–1]. Through judicious selection of parameters, an MRG can have a period as high as ηk – 1. As a generalization of LCGs, MRGs share many of the same properties. They have similar lattice structures, and certain MRGs exhibit strong correlations between pseudorandom numbers separated by large lags.
L’Ecuyer, Blouin and Couture (1993) performed an extensive search for good MRGs. One that they found is
[5.18]
This has period η7 – 1 ≈ 2217 and exhibits generally good lattice properties for dimensions up to 20. It can be efficiently implemented on a 32-bit computer, although this is less of a concern now that 64-bit computers are common.