Testing the PDH Random Numbers

Dr. Michael Mascagni, Professor of Computer Science, Florida State University


Our approach was to subject the random numbers provided to us by PDH, International, to a battery of statistical tests that we use to determine the quality of pseudorandom numbers.  As such the PDH numbers, heretofore referred to as kk0 for the file name in which PDH provided their 100 megabits of putatively random bits, were run through various tests along side several generators from our Scalable Parallel Random Number Generators (SPRNG) library.  In short, we conclude that the kk0 bits behave as random as the highest quality pseudorandom number generators.

The random numbers tested include:

  1. the kk0 bits
  2. the LCG random number generator from SPRNG
  3. the LCG64 random number generator from SPRNG
  4. the PMLCG random number generator from SPRNG
  5. the LFG random number generator from SPRNG
  6. the MLFG random number generator from SPRNG
  7. the CMRG random number generator from SPRNG
  8. the Random() random number generator from UNIX

All the SPRNG random number generators are known to be high-quality random number generators, while the Random() random number generator is known to have detectible defects.  The rationale was to have both good and bad generators to see where the kk0 bits compare.  In addition to just using the bits in the kk0 file, we also constructed 16-bit words by taking the bits in kk0 in reverse order, and by taking shifted versions of kk0.  We also created a "LCG twisted kk0" stream that was made up of the most-significant bits from kk0 and the least-significant bits from LCG.  All this was done so as to search for deficiencies that may lurk in unanticipated registrations of the kk0 bits.

Several difference batteries of tests were carried out on the generators, including tests from SPRNG, the DIEHARD tests (as modified for SPRNG), the NIST tests, and certain empirical tests found in Knuth's chapter on random number testing.  The SPRNG tests are reported in the file sprngtest.xls and included the following specific tests, which also include the Knuth tests:

  1. Collisions Test
  2. Coupon Collector's Test
  3. Equidistribution TestGap Test
  4. Maximum-of-t Test
  5. Permutation Test
  6. Poker Test
  7. Run Test
  8. Serial Correlation Test
The conclusions from these tests specifically are that all the kk0 and SPRNG generators pass the tests while Random() fails two of the gap tests.
 
We also carried out the following DIEHARD tests on these generators.  The complete list of tests within the DIEHARD suite is:
  1. 3D Sphere
  2. Bit Stream
  3. Birthday Spacing
  4. Count-the-1's on Stream
  5. Count-the-1's on Byte
  6. Craps
  7. DNA
  8. Minimum Distance
  9. OPSO
  10. OQSO
  11. Overlapping 5-Permutation
  12. Overlapping Sum
  13. Parking Lot
  14. Rank31
  15. Rank32
  16. Rank68
  17. Squeeze
The results can be found in the file diehardtest.xls.  First, it is important to note that the kk0 bits were too few in number to apply the Count-the-1's on Stream, DNA, OPSO, OQSO, and Rank68 tests. Unfortunately, these tests are considered the most stringent of the DIEHARD tests; however, the results from the other DIEHARD tests for kk0 are consistent with the SPRNG test results.  It is also important to not that
 
Finally, we also performed the NIST test suite on the kk0 numbers and the other generators.  Those test results are summarized in the files kk0.xls and kk0vsrg.xls.  The first of these files contains results from just the kk0 bits.  However, we took many different subsamples of these bits, which accounts for the large size of this file.  The second file shows the explicit comparison between two of the kk0 streams and the other tested generators.  The specific NIST tests performed were:
  1. Frequency
  2. Block Frequency
  3. Cusum
  4. Runs
  5. Rank
  6. FFT
  7. Aperiodic-Template
  8. Periodic-Template
  9. Universal
  10. Apen
  11. Random-Excursion
  12. Random-Excursion-V
  13. Serial
  14. Lempel-Ziv
As with the other two test suites, these results for kk0 are consistent with the results for the SPRNG generators.  However, in these test results we actually have performed many of each test, and the number reported for these tests is not just a raw score/probability, as above, but is the percentage of the tests that are passed in the group of each test.

References to Statistical Tests:

  1. The tests described in the chapter on random number generation in Donald Knuth's Art of Computer Programming, volume 2, Seminumerical Algorithms.

  2. The DIEHARD suite of tests developed by George Marsaglia.

  3. The suite of tests developed at the National Institute of Standards and Technology's (NIST) Information Technology Laboratory.

  4. A paper written by myself and two colleagues on the SPRNG test suite and testing random numbers in parallel, this paper has been submitted for publication in Parallel Computing.