Parallel use of multiplicative congruential random number generators

On parallel processors or in distributed computing environments, generating and sharing one stream of random numbers for all parallel processing elements is usually impractical. A more attractive method is to allow each processing element to generate random numbers independently. This paper investigates parallel use of multiplicative congruential generators. We analyze the leapfrog. the regular spacing, and the random spacing methods. Our results show: (1) The leapfrog method can result in multipliers of low spectral values. (2) In the random spacing method, the minimal distance between n substreams is only 1/n(2) of cycle length in average. (3) The regular spacing method can result in strong correlation between substreams if the starting points alpha(j)x(o) (mod m) are poorly selected. We then suggest selecting multiplier a and factor alpha based on their k-dimensional spectral values and the minimal distance between substreams of these generators. (C) 2006 Elsevier B.V. All rights reserved.