### NIST Tests

The National Institute of Standards and Technology has created several publications on random number generators under the category of computer security, along with a statistical test suite for assessing the quality of random and pseudo-random number generators [6] and [7]. This test suite is a command-line application that prompts the user with various testing options, and was simple to port to Windows 7 and Windows XP.

This test suite was used to analyze the five RNG algorithms presented above. Each algorithm was used to generate an ASCII file with 100 million bits, 32-bits per line. Each 32-bit value was generated either 1-bit at a time, or 16-bits at a time. Each algorithm was assessed at 10K, 100K and 1M bits, and run over 100 bit streams for each. The results of these tests are presented in Table 7.

The measurements in Table 7 show that using the Windows C **rand()** function to generate 1-bit per function call performs very poorly, failing most of the tests. Contrasting, at 15-bits per call it passes all of the NIST tests at large array size of 1 million bits -- one of the best results. These measurements correlate well with the earlier measurements, confirming that the Windows C **rand()** function can perform poorly or can perform well, depending on how it is used.

The other four RNGs from [4] perform very well, only marginally failing a few tests, and showing little difference between generating 1-bit or 16-bits per function call. Mersenne twister [5] is the best performer at 100K bits, and passes all of the tests at 1 million bits.

### Affect on Algorithm Performance

Performance of algorithms can vary significantly with variance of input data sets. Tables 8 through 13 show measured performance of various sorting algorithms discussed in [1], [2], [3] and [8] as input data sets are varied in size and the quality of randomness. STL **sort()** and **stable_sort()** are examined because **sort()** uses Heap Sort and **stable_sort()** uses Merge Sort.

Performance measurements shown in Tables 7 through 13 exhibit that STL **sort()** varies the most by as much as 2.3X, followed by Binary-Radix Sort at 1.7X, STL **stable_sort()** and Stable Hybrid N-bit-Radix Sort at 1.4X. Insertion Sort and Selection Sort do not seem to vary in performance with variation in the input data statistics.

Binary-Radix Sort is faster than STL **sort()** with good random number distribution, but is slower with a poor distribution. STL **stable_sort()** is significantly slower than STL **sort()** with poor random number distribution. Stable Hybrid N-bit-Radix Sort is several times faster than STL **sort()** under all input data sets tested.