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

**generates 15 random bits, and three calls to**

**rand()****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;

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.

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.