Random numbers play a critical role in the verification of designs, allowing testers to apply stimuli and stress a system beyond the known boundary conditions. The C++ standard library supplies the random() function, which after seeding, produces a simple pseudo-random sequence. For many applications, this simple function is enough; alternatively, it is very limiiting if your application needs to grow and support different testing methods. Though there are many random number libraries freely available, most modern C++ applications utilize Boost, and the Boost libraries contain the Boost.Random library as a compile-only header library.
A glance in the boost/random/ directory can be intimidating at first. There are various header files with cryptic mathematical names, but at its heart, however, the library is easy to understand once you understand the background concepts and have a statistical reference at your side. There are two key concepts that you need to understand before setting out to use the library: generators and distributions.
Background
Based on the Boost.Random documentation, generators can be classified into roughly three variations:
- Uniform – number sequences uniformly distributed over a finite range
- Pseudo – numbers sequences generated by an algorithmic process that simulates random behavior
- Non-deterministic – number sequences generated by stochastic processes
Determining which type of generator is best for your application depends on many factors, but for most test applications the pseudo-random generator is adequate. Examples of the pseudo-random generators are minstd_rand and rand48, which are both declared in boost/random/linear_congruential.hpp. Refer to the boost documentation and header files for more information on the various generators available.
Distributions represent the distribution, or layout, of a sequence of numbers over finite interval based on the corresponding random variable of the same name. When selecting a distribution for your tests, refer to an undergraduate level Statistics textbook or your favorite statistical reference. Boost.Random supports a large number of statistical distributions, including, but not limited to:
- Normal
- Uniform
- Binomial
- Exponential
- Gamma
- Bernoulli
- Geometric
- Poisson
If you need a distribution or generator not included in Boost.Random, you can implement new classes that conform to the Boost.Random interface causing minimal change to your code. More often than not, the library already has a sufficient amount at your disposal. Popular pseudo-random generators, such as the linear feedback shift that is ubiquitous in hardware engineering (boost/random/linear_feedback_shift.hpp) are available out-of-the-box and ready to use with some simple template parameters at instantiations.
In the remainder of this post, I am going to demonstrate the use of generators and distributions in developing a simple class that generates pseudo-random numbers for time periods.
Generating Random Time Periods
When testing multi-threaded code or even just trying to understand concepts in the Boost.Threads library, I find that having the ability to quickly and easily generate random time intervals beneficial. One thread can be blocked for X milliseconds, another by Y milliseconds, allowing one to verify the behavior of the various synchronization mechanisms in Boost.Threads. Using boost::variate_generator, we can bind a generator to a distribution and create a random sequence of numbers representing time periods. I use a simple class like the RandomTimePeriod class listed below.
#ifndef RANDOMTIMEPERIOD_H
#define RANDOMTIMEPERIOD_H
#include <boost/random.hpp>
#include <boost/shared_ptr.hpp>
class RandomTimePeriod
{
private:
// accept default template param of 'int'
typedef boost::uniform_int<> distribution_type;
typedef boost::minstd_rand generator_type;
typedef boost::variate_generator< generator_type,
distribution_type > RandomNumberGenerator;
public:
RandomTimePeriod(int max_ms=100)
{
// Magic number 42 - if you don't understand this,
// look into Douglas Adams--now!
generator_type generator(42);
distribution_type distribution(0,max_ms);
_rng.reset(new RandomNumberGenerator(generator, distribution));
}
int next()
{
(*_rng)();
}
private:
boost::shared_ptr _rng;
};
#endif
The code above should be rather straightforward. Typedefs are used to make the constructor code more readable. The constructor takes a parameter specifying the max time period in milliseconds, and it constructs the random number generator member variable. The generator is passed the infamous value of 42 as its seed value, but in real test code one should provide a better method of obtaining a seed. Calling the next() method on a RandomTimePeriod object will return a pseudo-random number. Internally the random number generator is stored in a smart pointer so that when the object’s reference count reaches zero, the object is properly cleaned up. Very simple, right? The following driver program demontrates how to use the RandomTimePeriod class.
int main(int argc, char* argv[])
{
RandomTimePeriod rtp;
for( int i=0; i<25; ++i){
std::cout << rtp.next() << std::endl;
}
return 0;
}
Armed with a simple random number generator, we can now focus on creating better tests for the verification of our designs. Stay tuned for more tutorials on Boost libraries, including Boost.Thread.
