Skip to content

Five Easy Pieces #1 – Random Numbers

February 19, 2012

Introduction

This is the first article in a series of five, in each of which I will present a simple problem and show how it can be solved in C++. The solutions will illustrate various aspects of C++ and its Standard Library in what is hopefully an easily digestible form, and each will build on the solution to the previous problem.

You will need some basic knowledge of C++ in order to follow these articles, and I suggest if you want to learn from them, you equip yourself with a C++ compiler (instructions for how to install one for Windows are here) and try to write and compile code to solve  problem as (or before!)  I present the solution.


Problem

We’ll start with something very easy, but which has a surprising number of subtle gotchas. Write a C++ program which simulates throwing a 6-sided die, generating  a single random number in the range 1 to 6.  An example of it being used three times:

$ dice6
3
$ dice6
5
$ dice6
3

Hint: You will need to use the rand() and srand() functions declared in the cstdlib library header file.


Development

In order to solve this problem, you obviously need to be able to generate a random number in the range 1 to 6, and then print the number out. The C++ Standard Library, which comes with all C++ compilers, provides a function for generating random integers called rand(). Let’s try writing a very simple C++ program to use it:

#include <iostream>
using namespace std;

int main() { 
    cout << rand() << endl;
}

If you compile this program, you will get an error message very similar to this:

error: 'rand' was not declared in this scope

A declaration error like this means that you have tried to use a function or object that the compiler knows nothing about. Although the rand() function is in the Standard Library, the compiler doesn’t know this – you have to tell it that such a function exists by giving a declaration of it. You can do this most conveniently by including the Standard Library header file cstdlib:

#include <iostream>
#include <cstdlib>
using namespace std;

int main() {
    cout << rand() << endl;
}

If you compile and run this program, you will find that it has two problems. First, it prints out a random number, but that number is (probably) not in the range 1 to 6 – on my system it is 41. Secondly, if you run the program multiple times, it always prints out the same number.  So you now have two further problems to solve – how to force the number into the range 1 to 6, and how to make it not be the same number each time.

The rand() function returns a value in the range 0 to RAND_MAX, where RAND_MAX is a constant defined in the cstdlib header file – an experiment; try printing it out to see what the value is on your system. It’s normally quite  a large number, and whenever you are faced with  a problem involving transforming a large range into a smaller one, you should be thinking modular arithmetic, which is arithmetic based on the remainder when you divide. For example, 8 divided by  6 gives you a remainder of 2, and any number divided by 6 can only have the remainders 0,1, 2, 3, 4 or 5, so to get the numbers 1 to 6, we need to divide by 6 and add 1 to the remainder.

C++ has a remainder operator – the % operator, which works only on integers, so 8 % 6 gives the result 2. Using this, you can rewrite your program:

#include <iostream>
#include <cstdlib>
using namespace std;

int main() {
    cout << 1 + rand() % 6 << endl;
}

This solves the first issue – it now generates a number in the range 1 to 6, but not the second – it still always generates the same number. In order to understand how to fix this, you need to know a little about how C++ (and other computer languages) generates random numbers.

Digital computers typically generate their random numbers by computation. Unfortunately, you cannot generate true random numbers by computation alone; you need a source of true randomness which can typically only be obtained by observing quantum events. How to do this is outside the scope of this article, but you can buy surprisingly cheap devices that do this for you. The numbers generated by functions like rand() are therefore only pseudorandom, but they will server for many purposes.

In outline, the system used to generate random numbers via rand() looks like this:

int seed = 1;

int rand() {
    return ++seed;   // calculation
}

A static variable is seeded with an initial value and each time you call rand() a calculation is performed on it (adding 1 to it, in this example), and the result of the calculation becomes the new value of the seed, and is thus used in the next call to rand().

It’s easy to see that the (obviously silly)  implementation or rand() above always produces the same sequence of "random" numbers, and the same is true of the real implementation of rand(). Try changing your program so that instead of writing out one dice throw, it writes out three:

#include <iostream>
#include <cstdlib>
using namespace std;

int main() {
  for( int i = 0; i < 3; i++ ) {
    cout << 1 + rand() % 6 << endl;
  }
}

 

If you run this, you should see that it always produces the same sequence of psedorandom numbers – on my system it always outputs 6, 6, 5. This is because, as with the simple, silly,  generator I showed above, each  pseudorandom number depends on the number before it – if you want a different sequence of numbers, you have to begin from a different starting point. This is what the srand() function does – it changes the seed value with which the pseudorandom sequence starts. – Try modifying your program to look like this:

#include <iostream>
#include <cstdlib>
using namespace std;

int main() {
  srand( 12345 );
  for( int i = 0; i < 3; i++ ) {
    cout << 1 + rand() % 6 << endl;
  }
}

If you compile this code, and run it multiple time, you should see that you get a different sequence than if you had not called srand() at all (doing this is actually defined as being equivalent to calling srand(1)) but you still get the same sequence each time.

In order to get a  sequence that differs each time, you obviously need to use srand() to set the seed value to a potentially different value each time the program is run.  Unfortunately, getting such a value is difficult. There are basically two more or less convenient sources – the current time, and the process id of your executing code, which is an integer allocated by the operating system and tends to be different each time you start  a process.  Getting the process id is, unfortunately, operating-system specific, so for portable code you are stuck with using the current time.

The C++ library supplies a number of time-related functions, but the one you need to use is time(). This returns a value of type time_t (which is some suitable integer type), which is the number of seconds since some fixed point in the past.  You can, optionally, pass a pointer to a time_t object, so both of these would fill in the object t1:

time_t t1 = time( NULL ); 
time_t t1;
time( & t1 );

The time functions are all declared in the ctime header file, so to seed the random number generator with the current time, your code should look like this:

#include <iostream>
#include <cstdlib>
#include <ctime>
using namespace std;

int main() {
  srand( time( NULL ) );
  for( int i = 0; i < 3; i++ ) {
    cout << 1 + rand() % 6 << endl;
  }
}

If you compile and run this code, you should see that each run provides a different sequence of random numbers. That is unless you execute the program very quickly twice in succession, in which case you will get the same sequence repeated. This is because the time() function has a granularity of 1 second – if you call it twice within 1 second, you will get the same time_t value  returned from it, and the random number generator will be seeded with the same value. There is no easy way round this, except for using the process id in combination with the current time. Here’s a version that does that for the Windows operating system:

#include <iostream>
#include <cstdlib>
#include <ctime>
#include <windows.h>
using namespace std;

int main() {
  srand( time( NULL ) * GetCurrentProcessId() );
  for( int i = 0; i < 3; i++ ) {
    cout << 1 + rand() % 6 << endl;
  }
}

This now (probably) produces different sequences each time it is run, at the expense of portability.


Conclusion

The final solution to the initial problem looks like this:

#include <iostream> #include <cstdlib> #include <ctime> #include <windows.h> using namespace std; int main() { srand( time( NULL ) * GetCurrentProcessId() ); cout << 1 + rand() % 6 << endl; }

 

If you implemented this,  hopefully you will have learned the following:

  • Digital computers can only generate pseudorandom numbers.
  • The C++ Standard Library supplies the srand() and rand() functions to generate such numbers.
  • You need to seed the random number generator.
  • Time and process id can provide suitable seeds.

In the next article, I’ll look at building on this to write a program that lets you pick various values at random, from a variety of sources.

Advertisements

From → c++, linux, tutorial, windows

Leave a Comment

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: