by Victor J. Duvanenko
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.

The following method is used 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.

Full Story

Related Stories
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