The random number generators provided in SPRNG are expected to be used in large-scale Monte Carlo simulations, and so we need to ensure that they are of high quality by theoretical analyses and empirical tests.
Theoretical AnalysesPseudorandom number sequences depend on a finite number of states, and so they have a finite period after which the random number sequence repeats. Clearly, it is important that the sequences have a much larger period than the length of the sequence that will be used. Usually the period of the generators can be determined theoretically, and are given in the section describing the generators.
In a parallel random number generator, we need to ensure that are is no correlation between different random number streams. For example, it should not so happen that most of the random numbers streams generate high random numbers in similar positions in the sequence. There are some theoretical analyses that discuss the independence of streams, as described in papers by Percus and Kalos and Mascagni, et al. The generators currently available in SPRNG satisfy the recommendations based on these theoretical tests.
The empirical tests can be grouped into two general categories as described below:
- A single stream of parallel random numbers should pass all the tests applicable to a serial stream. We shall discuss this issue first. The basic idea behind these tests of randomness is that the random number streams obtained from a generator should have the properties of a sample drawn from a uniform distribution. Tests are designed so that the expected value of some test statistic is known for the uniform distribution. The empirically generated random number stream is then subjected to the same test, and the statistic obtained is compared against the expected value. While a boundless number of tests can be constructed, certain tests have become popular and are accepted as the de facto standard. Generators that pass such tests are considered "good". The series of tests proposed by Knuth and the DIEHARD tests implemented by Marsaglia are practically considered the standard tests.
These tests check a random number stream for the uniformity of the stream and for correlations between numbers in the stream. In a parallel random number generator, we include the additional restriction that there should not be correlations between different random number streams. For example, it should not so happen that most of the random numbers streams generate high random numbers in similar positions. We wish to test our generators empirically, in addition to the theoretical analyses mentioned above. The tests we have conducted are modifications of the ideas for serial streams. If we interleave two streams such that the new stream generated has alternate numbers from the same stream, then this new stream should pass the tests for a serial random number stream if the original streams were not correlated. We perform such tests on several pairs of streams and observe whether the test statistics are acceptable. We can generalize this scheme to interleaving several random number streams at a time.
Physical Model Tests
- Random number generators that pass the statistical tests mentioned above do not always perform well in large-scale Monte Carlo simulations. It is best to test the random number generator in an application similar to where it will be used. We have subjected our generators to ISING model tests and random walk tests. The exact solution for these tests are known, and the tests also have the structure of practical applications. Thus they are good measures of the quality of the generators. We hope that our results will give the computational scientist a measure of the expected biases in the simulation.
We have performed these physical model tests using both, single streams and multiple streams in the simulation. The latter tests probe for correlations between streams.