Computer Science 2611
Fall 2004
Laboratory Assignment 6

Handed out: 10/25/04

Note. This is a fairly long assignment, and will take some time to do. Schedule extra time to work on it. It is likely that you will have some questions. Be sure to ask. Attend the lab and ask questions there.

Pseudo-random number generators

Sometimes it is useful for a computer to produce a random number. Most computers do not have the ability to produce a genuinely random number, but there are methods for creating numbers that are apparently random.

The idea is to produce a function which we will call next. You start with an integer called the seed. Define r₀ to be the seed. Then define

r₁ = next(r₀)
r₂ = next(r₁)
r₃ = next(r₂)

x₁ = r₁ / N
x₂ = r₂ / N
x₃ = r₃ / N

For example, suppose that function next is defined so that next(n) = (17*n + 1) mod 23, where 'mod' is the remainder operator (% in C++). Then next(n) is always less than 23. Suppose the seed is chosen to be 2. Then the sequence of numbers is

r₀ = 2
r₁ = next (2) = 12
r₂ = next (12) = 21
r₃ = next (21) = 13
...

x₁ = 12/23 = 0.5217
x₂ = 21/23 = 0.9130
x₃ = 13/23 = 0.5652
...

Notice that the integers in this sequence will never be larger than 22. Also, the sequence repeats after a while. It goes 12, 21, 13, 15, 3, 6, 11, 4, 0, 1, 18, 8, 22, 7, 5, 17, 14, 9, 16, 20, 19, 2, 12, 21, 13, 15, ... You do not want to use so many pseudo-random numbers that the sequence starts to repeat.

Different pseudo-random number generators use different functions next. One kind of function uses next(n) = (a*n + b) mod c, where a and c are prime numbers, a < c and b < c. Generally, you choose c to be fairly large, so that it takes a long time before the sequence starts to repeat. But you must keep it small enough that performing the required arithmetic does not overflow the capacity of the integers that you are using.

A simple approach to a pseudo-random number generator

Once you have a next function, you can create a random number generator. For example, you might define

   long next(long n)
   {
     return (14983*n + 17) % 29989;
   }

   int nextrandom(long& seed)
   {
     seed = next(seed);
     return double(seed)/29989.0;
   }

Pseudo-random number generating objects

The preceding approach works, but it requires you to manage the seed variable yourself. In effect, you find yourself concerned with the details of how to generate pseudo-random numbers just to be able to use a pseudo-random number generator. The object-oriented approach lets you encapsulate variables and operations into an object, so that anyone who wants to use the object just asks the object to do the job.

You can create objects that generate pseudo-random numbers by creating a class. Let's call the class Random. Class Random has one public method called getnext. If R is a random number generator object, then R.getnext() returns the next pseudo-random real number (between 0 and 1) in the sequence for random number generator R. R must remember its current value, starting with the seed. The getnext method must update the current value that R is holding, so that several calls to R.getnext() produce different numbers.

For example, here is a function that produces the sum of n pseudo-random bits. It is only given as an example of using a pseudo-random number generator; this function will not be part of your assignment.

   int randomSum(int n)
   {
     int k, sum;
     Random R;    // Create the random number generator object R.

     k = 0;
     sum = 0;
     while(k < n) {
       sum = sum + ((int)(2*R.getnext());
       k++;
     }
     return sum;
   }

Notice that the details of how things are done are gone. We do not maintain the seed variable ourselves. That makes this part of the program easier to write.

Here is another example function. It rolls a die, obtainig a result that is an integer from 1 to 6. It does not want to create a new random number generator for each roll of the die, so it has a random number generator as a parameter, and uses that object to get a random number. Objects are almost always passed by reference. Since the random number generator is an object, it is passed by reference. That is very important.

   int cointoss(Random& R)
   {
     return (int)(6*R.getnext()) + 1;
   }

Assignment, part 1. A pseudo-random number generator class

Write class Random. Put the class in file random.h. Do not put the method implementations there. Put them in file random.cpp.

To do this, ask yourself what information an object of class Random needs to rember between calls to getnext. Create a variable that holds the required information. Do not add any more variables later. Remember only what you really need to remember.

Write the getnext method. You will need a heading for it in random.h, and a definition of it in random.cpp. Remember to call it Random::getnext when you are writing random.cpp.

Include two public constructors. Constructor Random() creates a random number generator with a default seed. Put something in the seed. Constructor Random(s) creates a random number with seed s, where s is an integer.

Assignment, part 2: Using the random number generator

Write a program that simulates games of Craps. It should read an integer n from the user and play n games of Craps. At the end of the games, it should report how many of the games were passed, and how many did not pass, and the fraction of the games that passed.

The rules of Craps are as follows. The game is played with two dice. The player throws the dice to begin. If the outcome (the sum of the dice) is 7 or 11, the player passes (wins), and the game is over. If the outcome is 2, 3 or 12, the player does not pass, and the game is over.

If the outcome of the first throw is anything except 2,3,7,11 or 12, then the outcome of the first throw becomes the players point. The player repeatedly tosses the dice until either he or she throws a value equal to the point (in which case the player passes) or the player throws a 7 (in which case the player does not pass).

Here is a sample output. For each game, the sequence of dice sums thrown should be shown. They are shown in parentheses in front of the final result.

    How many games shall I play?  4
    Game 1. (7) Pass
    Game 2. (3) No pass
    Game 3. (4 8 5 7) No pass
    Game 4. (8 10 8) Pass

    There were 2 passes and 2 nonpasses, for a fraction of 0.500 passes.

Break your program into simple functions. For example, you will want a function that throws a die. Do not create a new random number generator object for each throw of the die. Create and use one object throughout, and pass it as a parameter to whichever function needs it. Your program should only create on random number generator object, regardless of how many games it plays.

Encapsulate the rules of Craps in a function (or possibly a function and another helper function), so that no other function needs to know anything about those rules.

Your program must be in a separate file from the random number generator. For example, write it in file craps.cpp. Include line

#include "random.h"

g++ -Wall -O random.cpp craps.cpp

Test your program, and look at the results. Do they look reasonable?

Warning. When you throw two dice, be sure to throw two separate dice. Do not just throw one die and double it. You will not get the same results. For example, if you throw one die and double it, you will always get an even number, and can never get 7.

Assignment, part 3. Improving the random number generator class

The random number generator that you have written always starts with the same seed. If you run the program twice in a row, you will get exactly the same results.

Modify class Random so that the parameterless constructor sets the initial seed to a value that is obtained from the computer's clock. You can do that as follows. Define function currentMicrosecond, which returns the number of microseconds since the last tick of the second clock.

#include <ctime>

long currentMicrosecond()
{
  timeval tv;
  gettimeofday(&tv, NULL);
  return tv.tv_usec;
}

#include <sys/timeb.h>
#include <memory>

long currentMicrosecond()
{
  timeb tb;
  memset(&tb, 0, sizeof(timeb));
  ftime(&tb);
  return 1000*tb.millitm;
}

Use the currentMicrosecond function to set the initial seed for the parameterless constructor. Try your Craps program. Does it produce different results now when you run it twice?

If you are testing a program, and something goes wrong, you want to be able to duplicate the results over and over, so that you can find out what is happening. For that reason, when you are testing a program that uses a pseudo-random number generator, you start with a fixed seed. Only later, when you use the program, do you attempt to randomize the results more.

Writing the program

Do not try to write the final version before testing anything. That will take more time than developing your program in steps. Implement the program as follows.

1. Write random.h and random.cpp. Write a tester (testrandom.cpp) that tests the random number generator. Get several pseudo-random numbers, and print them. Do they look reasonable?

2. Write craps.cpp so that it plays one game of craps. Test it. Does it appear to work? Be sure to print the rolls of the dice. You can do this in two parts.

   1. Print the rolls of the dice in any desired (simple) form.

   2. Improve things so that the rolls of the dice are shown in parentheses, on a single line, followed by the result of the game.

3. Now modify craps.cpp so that it reads a number n from the user and plays n games. Do not bother with the final report of the number of games passed, the number not passed and the fraction passed.

4. Now add counting of passes and no-passes. You will (hopefully) have a function that plays one game. How can you ask that function to tell you whether the game was a pass or a no-pass?

What to turn in

Turn in your final version, with all of the parts done. Turn in four files, random.h, random.cpp, testrandom.cpp and craps.cpp. I expect to see testrandom.cpp even though it is not part of the final program. Testing is very important, and you need to test individual components separately, not just the finished program as a whole.