1995 | OriginalPaper | Chapter
Parallel Pseudorandom Number Generation Using Additive Lagged-Fibonacci Recursions
Authors : Michael Mascagni, M. L. Robinson, Daniel V. Pryor, Steven A. Cuccaro
Published in: Monte Carlo and Quasi-Monte Carlo Methods in Scientific Computing
Publisher: Springer New York
Included in: Professional Book Archive
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
We study the suitability of the additive lagged-Fibonacci pseudorandom number generator for parallel computation. This generator has a relatively short period with respect to the size of its seed. However, the short period is more than made up for with the huge number of full-period cycles it contains. We call these different full-period cycles equivalence classes. We show how to enumerate the equivalence classes and how to compute seeds to select a given equivalence class. The use of these equivalence classes gives an explicit parallelization suitable for a fully reproducible asynchronous MIMD implementation. To explore such an implementation we introduce an exponential sum measure of quality for the additive lagged-Fibonacci generators used in serial or parallel. We then prove the first non-trivial results we are aware of on this measure of quality.