Channels ▼
RSS

Design

Algorithm Improvement through Performance Measurement: Part 5


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.

Table 7: Number of NIST tests failed. "*" indicates a fatal error during test run producing no results

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.

Table 8: STL sort()

Table 9: STL stable_sort()

Table 10: Binary-Radix Sort [2]

Table 11: Stable Hybrid N-bit-Radix Sort [3]

Table 12: Insertion Sort [8]

Table 13: Selection Sort [8]

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.


Related Reading


More Insights






Currently we allow the following HTML tags in comments:

Single tags

These tags can be used alone and don't need an ending tag.

<br> Defines a single line break

<hr> Defines a horizontal line

Matching tags

These require an ending tag - e.g. <i>italic text</i>

<a> Defines an anchor

<b> Defines bold text

<big> Defines big text

<blockquote> Defines a long quotation

<caption> Defines a table caption

<cite> Defines a citation

<code> Defines computer code text

<em> Defines emphasized text

<fieldset> Defines a border around elements in a form

<h1> This is heading 1

<h2> This is heading 2

<h3> This is heading 3

<h4> This is heading 4

<h5> This is heading 5

<h6> This is heading 6

<i> Defines italic text

<p> Defines a paragraph

<pre> Defines preformatted text

<q> Defines a short quotation

<samp> Defines sample computer code text

<small> Defines small text

<span> Defines a section in a document

<s> Defines strikethrough text

<strike> Defines strikethrough text

<strong> Defines strong text

<sub> Defines subscripted text

<sup> Defines superscripted text

<u> Defines underlined text

Dr. Dobb's encourages readers to engage in spirited, healthy debate, including taking us to task. However, Dr. Dobb's moderates all comments posted to our site, and reserves the right to modify or remove any content that it determines to be derogatory, offensive, inflammatory, vulgar, irrelevant/off-topic, racist or obvious marketing or spam. Dr. Dobb's further reserves the right to disable the profile of any commenter participating in said activities.

 
Disqus Tips To upload an avatar photo, first complete your Disqus profile. | View the list of supported HTML tags you can use to style comments. | Please read our commenting policy.
 

Video