A FAST, HIGH-QUALITY, AND REPRODUCIBLE PARALLEL LAGGED-FIBONACCI PSEUDORANDOM NUMBER GENERATOR

We study the suitability of the additive lagged-Fibonacci pseudorandom number generator for parallel computation. This generator has relativ ely short period with respect to the size of its seed. However, the sh ort period is more than made up for with the huge number of full-perio d cycles it contains. These different full-period cycles are called eq uivalence classes, We show how to enumerate the equivalence classes an d how to compute seeds to select a given equivalence class. In additio n, we present some theoretical measures of quality for this generator when used in parallel. Next, we conjecture on the size of these measur es of quality for this generator. Extensive empirical evidence support s this conjecture. In addition, a probabilistic interpretation of thes e measures leads to another conjecture similarly supported by empirica l evidence. Finally we give an explicit parallelization suitable for a fully reproducible asynchronous MIMD implementation. (C) 1995 Academi c Press, Inc.