Parallel use of multiplicative congruential random number generators

This paper investigates parallel use of multiplicative congruential generators by analyzing the leapfrog, the regular spacing, and the random spacing methods and suggests selecting multiplier a and factor α based on their k -dimensional spectral values and the minimal distance between substreams of these generators.

Abstract

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/n2 of cycle length in average. (3) The regular spacing method can result in strong correlation between substreams if the starting points αjx0 (modm) are poorly selected. We then suggest selecting multiplier a and factor α based on their k-dimensional spectral values and the minimal distance between substreams of these generators.