Parallel linear congruential generators with SophieGermain moduli
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. 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. Recently, one of the authors of this paper [M. Mascagni, Parallel linear congruential generators with prime moduli, Parallel Comput. 24 (1998) 923936] developed an explicit parameterization of prime modulus LCGs for use in parallel computations. 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. 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. 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 SophieGermain prime modulus LCGs. While the choice of Mersenne primes trades off initialization time for generation time, the choice of SophieGermain primes not only largely reduces initialization time but also provides competitive generation time when an appropriately chosen SophieGermain primes are used. The resulting SophieGermain prime modulus LCGs have been tested, and incorporated into the Scalable Parallel Random Number Generators SPRNG library [SPRNG. Scalable parallel random number generators, http://sprng.fsu.edu], a widely used random number generation suite for parallel, distributed, and grid-based Monte Carlo computations [M. Mascagni, A. Srinivasan, Computational infrastructure for parallel, distributed, and grid-based Monte Carlo computations, Lect. Notes Comput. Sci. 2907 (2004) 3952].
parallel random number generation mersenne prime sophiegermain prime prime modulus linear congruential generators