Title

Parallel Linear Congruential Generators with Prime Moduli

Document Type

Article

Publication Date

6-1-1998

Department

Computing

Abstract

Linear congruential generators (LCGs) remain the most popular method of pseudorandom number generation on digital computers. Ease of implementation has favored implementing LCGs with power-of-two moduli. However, 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 becomes an even more compelling issue. We use a full-period exponential sum as the measure of stream independence and present a method for producing provably independent streams of LCGs in parallel by utilizing an explicit parameterization of all of the primitive elements module a given prime. The minimization of this measure of independence further motivates an algorithm required in the explicit parameterization. We describe and analyze this algorithm and describe its use in a parallel LCG package. (C) 1998 Elsevier Science B.V. All rights reserved.

Publication Title

Parallel Computing

Volume

24

Issue

41035

First Page

923

Last Page

936