Computer Science 2611
Spring 2003
Laboratory Assignment 5

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₂)

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

Notice that the numbers 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, ...

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 seed;
   }

A pseudo-random bit is either 0 or 1, each about equally likely. You could use your nextrandom function to compute the sum of n pseudo-random bits as follows.

   int randomSum(int n)
   {
     int k, sum;
     int seed = 3245;

     k = 0;
     sum = 0;
     while(k < n) {
       sum = sum + (nextrandom(seed) % 2);
       k++;
     }
     return sum;
   }

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 random number 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, but this time using a random-number genorator object of class Random. 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 + (R.getnext() % 2);
       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 performs a "coin toss", producing either true or false. It does not want to create a new random number generator for each coin toss, so it has a random number generator as a parameter, and uses that object to get a random number. Notice that, since the random number generator is an object, it is passed by reference. That is very important.

   bool cointoss(Random& R)
   {
     return R.nextRandom() % 2;
   }

A pseudo-random number generator class

Here is a definition of class Random. It is broken into two files called random.h and random.cc. Copy it, and create those to files.

// File random.h

class Random
{
  public:

  //------------------------------------------------------------------
  // The constructor produces a pseudo-random number generator with
  // a default seed.
  //------------------------------------------------------------------

  Random();

  //------------------------------------------------------------------
  // getnext() produces the next pseudo-random number in the sequence.
  // Each call to getnext() produces another number from the sequence.
  //------------------------------------------------------------------

  long getnext();

  //===============================================================
  private:

  // Variable current holds the current value in the sequence.

  long current;

  // next(x) is the value that follows x in the sequence.

  long next(long x);
  };

  
// File random.cc

#include "random.h"

Random::Random()
{
  current = 5912;
}

long Random::getnext()
{
  current = next(current);
  return current;
}

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

Assignment: Using the random number generator

Write a program that plays 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. If the outcome is 2, 3 or 12, the player does not pass.

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.

    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 (just take a pseudo-random number mod 6, and add 1). 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.

Encapsulate the rules of Craps in a function, so that no other function needs to know anything about those rules.

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

#include "random.h"

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

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.

Improving the random number generator class

The random number generator that I have provided 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 it has a constructor with a single parameter, which is the seed. Make it set current to the value of that parameter.

Modify your craps program so that it sets the seed according to the system clock. Use the following include and function to get the system time, in milliseconds.

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

long timeInMilliseconds()
{
  struct timeb tb;
  memset(&tb, 0, sizeof(struct timeb));
  ftime(&tb);
  return tb.millitm + 1000*(labs(tb.time) % 100000);
}