Fast combined multiple recursive generators with multipliers of the form a = ±2q ±2r
Pierre L’Ecuyer, Renée Touzin · Winter Simulation Conference · 2000
We study a class of combined multiple recursive random number generators constructed in a way that each component runs fast and is easy to implement, while the combination enjoys excellent structural properties as measured by the spectral test. Each component is a linear recurrence of order k > 1, modulo a large prime number, and the coefficients are either 0 or are of the form a = ±2q or a = ±2q ±2r. This allows a simple and very fast implementation, because each modular multiplication by a power of 2 can be implemented via a shift, plus a few additional operations for the modular reduction. We select the parameters in terms of the performance of the combined generator in the spectral test. We provide a specific implementation.