The resulting Sophie–Germain prime modulus LCGs have been tested, and incorporated into the Scalable Parallel Random Number Generators SPRNG library, a widely used random number generation suite for parallel, distributed, and grid-based Monte Carlo computations. While the choice of Mersenne primes trades off initialization time for generation time, the choice of Sophie–Germain primes not only largely reduces initialization time but also provides competitive generation time when an appropriately chosen Sophie–Germain primes are used. In the current paper, we investigate the nature of the trade-off implicitly made in the choice of Mersenne primes by comparing them to parameterized Sophie–Germain prime modulus LCGs. In that paper, only Mersenne prime moduli were considered because of the existence of a fast modular multiplication algorithm for primes close to powers-of-two. This approach was based on an explicit enumeration of all the primitive roots modulo the prime modulus for use as unique multipliers in each parallel LCG. Recently, one of the authors of this paper developed an explicit parameterization of prime modulus LCGs for use in parallel computations.
Linear congruential generators (LCGs), the most common number-theoretic pseudorandom number generators, with both power-of-two and prime moduli are used in many popular implementations of pseudorandom number generators. Monte Carlo simulations are thought to be very easy to parallelize however, the quality of these parallel Monte Carlo computations depends greatly on the quality of the parallel random number generators used.
0 kommentar(er)
