Channels ▼
RSS

Parallel

Algorithm Improvement through Performance Measurement: Part 5



Algorithm Improvement through Performance Measurement: Part 1

Algorithm Improvement through Performance Measurement: Part 2

Algorithm Improvement through Performance Measurement: Part 3

Algorithm Improvement through Performance Measurement: Part 4

Algorithm Improvement through Performance Measurement: Part 5


Random numbers are used in many domains, from networking protocols, to cryptography, to selection of a starting point for integrated circuit place and route algorithms, simulations, and computer graphics. When benchmarking algorithm performance, arrays of random input data at times provide the worst case input (but sometimes do not). In this article, I explore several random-number generators (RNGs), along with their strengths and weaknesses, as well as their affects on performance of sorting algorithms.

I used the following method in In-place Hybrid N-bit-Radix Sort, and In-place Hybrid Binary-Radix Sortto generate random 32-bit unsigned values:


unsigned long randomValue = ((unsigned long)rand()) << 30 |
                                                ((unsigned long)rand()) << 15 |
                                                ((unsigned long)rand());

This method uses the built-in rand() function, which generates a random number in the range 0 to RAND_MAX ( which is 32767). Each call to rand() generates 15 random bits, and three calls to rand() are used to generate 32 random bits for the unsigned long data type (15 bits, 15 bits, and 2 bits). Function srand was first used to seed this pseudo-random generator -- to provide a consistent starting point so as to produce a repeatable sequence of random numbers to fill an array with.

I used a different random-number generator technique for all performance measurements in Stable Hybrid MSD N-bit-Radix Sort:


float f1 = ranX( &randState );              // 0.0 .. 1.0
float f2 = ranX( &randState );              // 0.0 .. 1.0
unsigned long tmp1   = (unsigned long)( (( 1 << 16 ) - 1 ) * f1 );
unsigned long tmp2   = (unsigned long)( (( 1 << 16 ) - 1 ) * f2 );
unsigned long result = ( tmp1 << 16 ) | tmp2;

where ranX() function can be either ran0(),ran1(), or ran2() function from [4], with ran2() used for performance measurements. This method generates 16 bits per ranX() function call. However, fewer number of bits could be generated per call by adding a masking operation as follows:


float f1 = ranX( &randState );              // 0.0 .. 1.0
unsigned long eightBits = (unsigned long)( (( 1 << 16 ) - 1 ) * f1 ) & 0xff;

Listing 1

This implementation generates 8 random bits per call to the random generation function, by taking eight least significant bits of the result. Bits other than the least significant ones could be retained by using a different mask followed by a right shift. To produce a 32-bit random number using this method, four results of 8 bits each would need to be generated and concatenated together as:


unsigned long result32bit = ( eightBit[ 0 ] << 24 ) | ( eightBit[ 1 ] << 16 ) |
                                            ( eightBit[ 2 ] <<  8 ) |   eightBit[ 2 ];

Table 1 shows the number of unique values that each of the random number generators created when filling an array of 100 million 32-bit unsigned elements. Windows C rand(), as well as three functions from [4] and Mersenne twister [5] are compared.

Table 1: Number of unique values within 100 million elements

In all cases, 32-bit unsigned array elements were generated by calling each function multiple times. For example, 1-bit at a time required 32 function calls to generate a 32-bit value; and 16-bits at a time required two function calls. The least significant bits were extracted and concatenated into a 32-bit value. For Table 1, an array of 100 million 32-bit values was generated. STL's unique() function was used to count the number of unique values within this array.

All of the functions were seeded with the same value of 2, negating it for ran0(), ran1(), and ran2() as they require. From this simple and fairly weak test (of using STL unique() function) it is evident that the Windows C rand() function can produce poor random number sequences, with only 4K unique numbers within the 100 million element array (only 0.004% unique). However, it can also produce sequences with a large percentage of unique values. This test is weak because it would get fooled by an incrementing 32-bit number sequence, which would have 100 million unique values, but would not be random. But, the test is adequate to detect this issue.

Table 1 shows a problem in the Windows C rand() function, that becomes especially evident when extracting 10 bits or fewer per function call. This does not seem to be a problem with only a single lower bit. When extracting 11 bits or more, C rand() function produced more than 92% of values that are unique.

The other four RNGs tested do not exhibit this issue no matter how many bits are extracted per function call. Their lower bits do not exhibit problems. These RNGs produce more than 97.7% of values that are unique.


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