Case Study: Random Number Generation

Case Study Random Number Generation

We now take a brief and hopefully entertaining diversion into a popular programming application, namely simulation and game playing. In this and the next section, we develop a game-playing program that includes multiple functions. The program uses many of the control statements and concepts discussed to this point.

---

The element of chance can be introduced into computer applications by using the C++ Standard Library function rand.

Consider the following statement:

i = rand();

The function rand generates an unsigned integer between 0 and RAND_MAX (a symbolic constant defined in the header file). The value of RAND_MAX must be at least 32767the maximum positive value for a two-byte (16-bit) integer. For GNU C++, the value of RAND_MAX is 214748647; for Visual Studio, the value of RAND_MAX is 32767. If rand TRuly produces integers at random, every number between 0 and RAND_MAX has an equal chance (or probability) of being chosen each time rand is called.

The range of values produced directly by the function rand often is different than what a specific application requires. For example, a program that simulates coin tossing might require only 0 for "heads" and 1 for "tails." A program that simulates rolling a six-sided die would require random integers in the range 1 to 6. A program that randomly predicts the next type of spaceship (out of four possibilities) that will fly across the horizon in a video game might require random integers in the range 1 through 4.

Rolling a Six-Sided Die

To demonstrate rand, let us develop a program (Fig. 6.8) to simulate 20 rolls of a six-sided die and print the value of each roll. The function prototype for the rand function is in . To produce integers in the range 0 to 5, we use the modulus operator (%) with rand as follows:

rand() % 6

 

Figure 6.8. Shifted, scaled integers produced by 1 + rand() % 6.

(This item is displayed on pages 253 - 254 in the print version)

 1 // Fig. 6.8: fig06_08.cpp
 2 // Shifted and scaled random integers.
 3 #include 
 4 using std::cout;
 5 using std::endl;
 6
 7 #include 
 8 using std::setw;
 9
10 #include  // contains function prototype for rand
11 using std::rand; 
12
13 int main()
14 {
15 // loop 20 times
16 for ( int counter = 1; counter <= 20; counter++ )
17 {
18 // pick random number from 1 to 6 and output it
19 cout << setw( 10 ) << ( 1 + rand() % 6 ); 
20
21 // if counter is divisible by 5, start a new line of output
22 if ( counter % 5 == 0 )
23 cout << endl;
24 } // end for
25
26 return 0; // indicates successful termination
27 } // end main

 

 6 6 5 5 6
 5 1 1 5 3
 6 6 2 4 2
 6 2 3 4 1

 

This is called scaling. The number 6 is called the scaling factor. We then shift the range of numbers produced by adding 1 to our previous result. Figure 6.8 confirms that the results are in the range 1 to 6.

---

Rolling a Six-Sided Die 6,000,000 Times

To show that the numbers produced by function rand occur with approximately equal likelihood, Fig. 6.9 simulates 6,000,000 rolls of a die. Each integer in the range 1 to 6 should appear approximately 1,000,000 times. This is confirmed by the output window at the end of Fig. 6.9.

Figure 6.9. Rolling a six-sided die 6,000,000 times.

(This item is displayed on pages 254 - 255 in the print version)

 1 // Fig. 6.9: fig06_09.cpp
 2 // Roll a six-sided die 6,000,000 times.
 3 #include 
 4 using std::cout;
 5 using std::endl;
 6
 7 #include 
 8 using std::setw;
 9
10 #include  // contains function prototype for rand
11 using std::rand;
12
13 int main()
14 {
15 int frequency1 = 0; // count of 1s rolled
16 int frequency2 = 0; // count of 2s rolled
17 int frequency3 = 0; // count of 3s rolled
18 int frequency4 = 0; // count of 4s rolled
19 int frequency5 = 0; // count of 5s rolled
20 int frequency6 = 0; // count of 6s rolled
21
22 int face; // stores most recently rolled value
23
24 // summarize results of 6,000,000 rolls of a die
25 for ( int roll = 1; roll <= 6000000; roll++ )
26 {
27 face = 1 + rand() % 6; // random number from 1 to 6
28
29 // determine roll value 1-6 and increment appropriate counter
30 switch ( face )
31 {
32 case 1:
33 ++frequency1; // increment the 1s counter
34 break;
35 case 2:
36 ++frequency2; // increment the 2s counter
37 break;
38 case 3:
39 ++frequency3; // increment the 3s counter
40 break;
41 case 4:
42 ++frequency4; // increment the 4s counter
43 break;
44 case 5:
45 ++frequency5; // increment the 5s counter
46 break;
47 case 6:
48 ++frequency6; // increment the 6s counter
49 break;
50 default: // invalid value
51 cout << "Program should never get here!";
52 } // end switch
53 } // end for
54
55 cout << "Face" << setw( 13 ) << "Frequency" << endl; // output headers
56 cout << " 1" << setw( 13 ) << frequency1
57 << "
 2" << setw( 13 ) << frequency2
58 << "
 3" << setw( 13 ) << frequency3
59 << "
 4" << setw( 13 ) << frequency4
60 << "
 5" << setw( 13 ) << frequency5
61 << "
 6" << setw( 13 ) << frequency6 << endl;
62 return 0; // indicates successful termination
63 } // end main

 

 Face Frequency
 1 999702
 2 1000823
 3 999378
 4 998898
 5 1000777
 6 1000422

 

---

As the program output shows, we can simulate the rolling of a six-sided die by scaling and shifting the values produced by rand. Note that the program should never get to the default case (lines 5051) provided in the switch structure, because the switch's controlling expression (face) always has values in the range 16; however, we provide the default case as a matter of good practice. After we study arrays in Chapter 7, we show how to replace the entire switch structure in Fig. 6.9 elegantly with a single-line statement.

---

Error-Prevention Tip 6.3

Provide a default case in a switch to catch errors even if you are absolutely, positively certain that you have no bugs!

 

Randomizing the Random Number Generator

Executing the program of Fig. 6.8 again produces

 6 6 5 5 6
 5 1 1 5 3
 6 6 2 4 2
 6 2 3 4 1

 

Notice that the program prints exactly the same sequence of values shown in Fig. 6.8. How can these be random numbers? Ironically, this repeatability is an important characteristic of function rand. When debugging a simulation program, this repeatability is essential for proving that corrections to the program work properly.

Function rand actually generates pseudorandom numbers. Repeatedly calling rand produces a sequence of numbers that appears to be random. However, the sequence repeats itself each time the program executes. Once a program has been thoroughly debugged, it can be conditioned to produce a different sequence of random numbers for each execution. This is called randomizing and is accomplished with the C++ Standard Library function srand. Function srand takes an unsigned integer argument and seeds the rand function to produce a different sequence of random numbers for each execution of the program.

Figure 6.10 demonstrates function srand. The program uses the data type unsigned, which is short for unsigned int. An int is stored in at least two bytes of memory (typically four bytes of memory on today's popular 32-bit systems) and can have positive and negative values. A variable of type unsigned int is also stored in at least two bytes of memory. A two-byte unsigned int can have only nonnegative values in the range 065535. A four-byte unsigned int can have only nonnegative values in the range 04294967295. Function srand takes an unsigned int value as an argument. The function prototype for the srand function is in header file .

Figure 6.10. Randomizing the die-rolling program.

(This item is displayed on pages 256 - 257 in the print version)

 1 // Fig. 6.10: fig06_10.cpp
 2 // Randomizing die-rolling program.
 3 #include 
 4 using std::cout;
 5 using std::cin;
 6 using std::endl;
 7
 8 #include 
 9 using std::setw;
10
11 #include  // contains prototypes for functions srand and rand
12 using std::rand; 
13 using std::srand; 
14
15 int main()
16 {
17 unsigned seed; // stores the seed entered by the user
18
19 cout << "Enter seed: ";
20 cin >> seed;
21 srand( seed ); // seed random number generator
22
23 // loop 10 times
24 for ( int counter = 1; counter <= 10; counter++ )
25 {
26 // pick random number from 1 to 6 and output it
27 cout << setw( 10 ) << ( 1 + rand() % 6 );
28
29 // if counter is divisible by 5, start a new line of output
30 if ( counter % 5 == 0 )
31 cout << endl;
32 } // end for
33
34 return 0; // indicates successful termination
35 } // end main

 

 Enter seed: 67
 6 1 4 6 2
 1 6 1 6 4

 

 

 Enter seed: 432
 4 6 3 1 6
 3 1 5 4 2

 

 

 Enter seed: 67
 6 1 4 6 2
 1 6 1 6 4

 

---

Let us run the program several times and observe the results. Notice that the program produces a different sequence of random numbers each time it executes, provided that the user enters a different seed. We used the same seed in the first and third sample outputs, so the same series of 10 numbers is displayed in each of those outputs.

To randomize without having to enter a seed each time, we may use a statement like

srand( time( 0 ) );

---

This causes the computer to read its clock to obtain the value for the seed. Function time (with the argument 0 as written in the preceding statement) returns the current time as the number of seconds since January 1, 1970 at midnight Greenwich Mean Time (GMT). This value is converted to an unsigned integer and used as the seed to the random number generator. The function prototype for time is in .

Common Programming Error 6.7

Calling function srand more than once in a program restarts the pseudorandom number sequence and can affect the randomness of the numbers produced by rand.

 

Generalized Scaling and Shifting of Random Numbers

Previously, we demonstrated how to write a single statement to simulate the rolling of a six-sided die with the statement

face = 1 + rand() % 6;

which always assigns an integer (at random) to variable face in the range 1 face images/U2264.jpg border=0> 6. Note that the width of this range (i.e., the number of consecutive integers in the range) is 6 and the starting number in the range is 1. Referring to the preceding statement, we see that the number = shiftingValue + rand() % scalingFactor;

where shiftingValue is equal to the first number in the desired range of consecutive integers and scalingFactor is equal to the width of the desired range of consecutive integers. The exercises show that it is possible to choose integers at random from sets of values other than ranges of consecutive integers.

Common Programming Error 6.8

Using srand in place of rand to attempt to generate random numbers is a compilation errorfunction srand does not return a value.