Parallelizable efficient large order multiple recursive generators

The general multiple recursive generator (MRG) of maximum period has been thought of as an excellent source of pseudo random numbers. Based on a kth order linear recurrence modulo p, this generator produces the next pseudo random number based on a linear combination of the previous k numbers. General maximum period MRGs of order k have excellent empirical performance, and their strong mathematical foundations have been studied extensively. For computing efficiency, it is common to consider special MRGs with some simple structure with few non-zero terms which requires fewer costly multiplications. However, such MRGs will not have a good “spectral test” property when compared with general MRGs with many non-zero terms. On the other hand, there are two potential problems of using general MRGs with many non-zero terms: (1) its efficient implementation (2) its efficient scheme for its parallelization. Efficient implementation of general MRGs of larger order k can be difficult because the kth order linear recurrence requires many costly multiplications to produce the next number. For its parallelization scheme, for a large k, the traditional scheme like “jump-ahead parallelization method” for general MRGs becomes highly computationally inefficient. We proposed implementing maximum period MRGs with many nonzero terms efficiently and in parallel by using a MCG constructed from the MRG. In particular, we propose a special class of large order MRGs with many nonzero terms that also have an efficient and parallel implementation.