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
|
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
|
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
|
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
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. |