We now mention some tests of parallel random number generators.
Exponential sums: The exponential sum (Fourier transform of the density) of a sequence is:
For a random sequence (for ). This fact can be used to test correlation within, and between, random number sequences [13, 16]. Consider two random sequences X and Y and define the exponential sum cross-correlation:
In each term of this sum, we find the difference between an element of each sequence at a fixed offset apart. If this difference were uniformly distributed, then we should have:
Parallel spectral test: Percus and Kalos  have developed a version of the spectral test for parallel linear congruential generators.
Interleaved tests: We create a new random sequence by interleaving several random sequences, and test this new sequence for randomness using standard sequential tests.
Fourier transform test: Generate a two dimensional array of random numbers with each row in the array consisting of consecutive random numbers from one particular sequence. The two dimensional Fourier transform can be performed. For a truly uncorrelated set of sequences the coefficients (except the constant term) should be close to 0.
Blocking test: In the blocking test we add random numbers from several streams as well as from within a stream. If the streams are independent, then the distribution of these sums will approach the normal distribution.
We now give some test results for the LCG with (parameterized) prime addend and a modified version of the LFG. Both of these generators performed acceptably in the sequential tests with random numbers. Preliminary results from other tests of PPRNG can also be found in the paper by Coddington .
We first tested the generators by interleaving about 1000 pairs of random sequences each containing about PRNs. Both the generators passed this tests. Next we simulated parallelism on the Ising model by using a different random sequence for each lattice site in the Metropolis algorithm. The LCG (with identical seeds) failed badly as can be seen from the dashed line in Fig. . We then generalized the statistical tests, interleaving 256 sequences at a time. The LCG again failed, demonstrating the effectiveness of these tests in detecting non-random behavior. The modified LFG passed these tests.
Figure: Plot of the actual error versus the internally estimated standard deviation of the energy error for Ising model simulations with the Metropolis algorithm on a lattice with a different Linear Congruential sequence at each lattice site. The dashed line shows the results when all the Linear Congruential sequences were started with the same seeds but with different additive constants. The solid line shows the results when the sequences were started with different seeds. We expect around 95% of the points to be below the dotted line (which represents an error of two standard deviations) with a good generator.
In the tests mentioned above, we had started each parameterized LCG with the same seed but used different additive constants. Even when we discarded the first million random numbers from each sequence, the sequences were still correlated. However, when we started the streams from different, systematically spaced seeds, the LCG passed all statistical tests (including parallel ones) with up to - numbers. We finally repeated the parallel Metropolis algorithm simulation with random numbers, and both generators performed acceptably, as can be seen from the solid line in Fig. .
Apart from verifying the quality of two particular generators, our results illustrate that it is commonplace for generators to pass some test and fail others. It is important to test parallel generators the way they will be seeded, since correlations in the seeding can lead to correlations in the resulting sequences.
The National Center for Supercomputing Applications
University of Illinois at Urbana-Champaign
Last modified: September 16, 1997