PARALLEL LINEAR CONGRUENTIAL GENERATORS WITH PRIME MODULI

Linear congruential generators (LCGs) remain the most popular method o f pseudorandom number generation on digital computers. Ease of impleme ntation has favored implementing LCGs with power-of-two moduli. Howeve r, prime modulus LCGs are superior in quality to power-of-two modulus LCGs, and the use of a Mersenne prime minimizes the computational cost of generation. When implemented for parallel computation, quality bec omes an even more compelling issue. We use a full-period exponential s um as the measure of stream independence and present a method for prod ucing provably independent streams of LCGs in parallel by utilizing an explicit parameterization of all of the primitive elements module a g iven prime. The minimization of this measure of independence further m otivates an algorithm required in the explicit parameterization. We de scribe and analyze this algorithm and describe its use in a parallel L CG package. (C) 1998 Elsevier Science B.V. All rights reserved.