Computer Science 2311
Fall 2007
Laboratory Assignment 7

Handed out: 10/22/07

Note. When you read this assignment, it will sound like a huge job. It is not really that large. Just tackle it a bit at a time, and keep things simple. Avoid making things overly complicated. If you do not see how to do something, ask questions. Look at notes to remember how to write in Java. If you are lost, try showing on paper what you are trying to accomplish. If you are unable to do that, ask for help.

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, or pseudo-random. For programming assignment 3 (part 2) you made use of a pseudo-random number generator from the Cinnameg library. There is also one in the Java library, a class called Random.

The idea of a pseudo-random number generator is to define a function next(n) that takes an integer argument and produces an integer result. You start with an integer called the seed. Define r0 to be the seed. Then define

r1 = next(r0)
r2 = next(r1)
r3 = next(r2)
etc. That gives you a sequence of integers r1, r2, r3, ...

For example, suppose that you define next(n) = (17*n + 1) mod 23. Suppose the seed is chosen to be 2. Then the sequence of numbers is

r0 = 2
r1 = next (2) = 12
r2 = next (12) = 21
r3 = next (21) = 13
...
Notice that next(2) = 12 because (17*2 + 1) mod 23 = 35 mod 23 = 12.

Since the integers in our sequence will all be less than 23, 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, since then it hardly looks random.

You can also get a pseudo-random real number between 0 and 1 by taking the integers and dividing by an integer that is just larger than the largest possible integer in the sequence. For example, for our simple function next(n) = (17*n + 1) mod 23, define real number xi = ri / 23. Then the sequence of real numbers, starting with seed 2, is

x1 = r1/23 = 12/23 = 0.5217
x2 = r2/23 = 21/23 = 0.9130
x3 = r3/23 = 13/23 = 0.5652
...

Different pseudo-random number generators use different functions next(n). One kind, called a linear congruential pseudo-random number generator, 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. You can use the fact that 19872889 and 10237763 are prime. They are about the right size, if you use type long for your arithmetic, not type int. Notice that 10237763 < 19872889. So you can define

next(n) = (10237763*n + b) mod 19872889.

Pseudo-random number generating objects

This section explains how you can use a pseudo-random number generator object, assuming that an appropriate class has already been created.

Suppose that there is a class called MyRandom that has two public things (and some number of private things). It has a constructor MyRandom(n), where n is an integer, that creates a new object with seed n. It also has a public method nextReal( ) that produces the next real number between 0 and 1. Each time you use the nextReal method, you get another pseudo-random number, as long as you do not get so many that the sequence repeats.

For example, the following function creates a pseudo-random number generator object called R and uses it to add up n pseudo-random numbers. It is only given as an example of using a pseudo-random number generator; this function will not be part of your assignment. 

   public static double randomSum(int n, int seed)
   {
     int k;
     double sum;
     MyRandom R = new MyRandom(seed);

     k = 0;
     sum = 0.0;
     while(k < n) {
       sum = sum + R.nextReal();
       k++;
     }
     return sum;
   }

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. 

   public static int rollDie(MyRandom R)
   {
     return (int)(6.0*R.nextReal()) + 1;
   }

Assignment, part 1: Write a pseudo-random number generator class

Write a definition of a pseudo-random number generator class. It should have the following components.

  1. A private variable of type long that remembers the current integer in the sequence.

  2. Private static constants a, b and c, which are the constants used in the next method. Define them as follows. (The word final means that you are not allowed to change them.) 

      private static final long a = 10237763;
  private static final long b = 17;
  private static final long c = 19872889;

  3. A private static method next(n) that returns the integer that follows n in the sequence. Here is a suggestion of the next method in that class. 

       private static long next(long n)
   {
     return (a*n + b) % c;
   }

  4. A public constructor that takes an integer seed and stores it into the variable (see item 1).

  5. A public method nextReal( ) that returns the next real number in the sequence, and also updates the variable (item 1) to hold the next integer in the sequence.

  6. A public method rollDie( ) that returns a pseudo-random integer from 1 to 6. (It should use nextReal( ). The example of rollDie above takes the random number generator as a parameter. But you do not need to do that here. Method rollDie now lives inside an object, and it should use that same object's nextReal( ) method. Do not declare rollDie to be static.

Write a clear, precise and concise contract for each method.

TEST YOUR CLASS. Write a main function that creates a pseudo-random number generator object and uses it to generate several random numbers. Try using rollDie several times. Do the results look reasonable? Do not proceed until this class appears to be working correctly.

Note. Java is very picky about where you define main. Put your MyRandom class in a file called Assn7.java. In that file, put two classes, the MyRandom class and another just called Assn7. Only make the Assn7 class public. So your program will be as follows, with ... indicating details that are left out. 

  public class Assn7
  {
    public static void main(String[] args)
    {
      ...
    }
  }

  class MyRandom
  {
    ...
  }

Assignment, part 2: Using the random number generator

The rules of Craps are described below. The second part of your assignment is to add another class to your program that simulates games of Craps. Your main program should read an integer n from the user and play n games of Craps. To play each game, it should call a static method play in the Craps class. At the end of the games, it should report how many of the games were passed, 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).

When a game is played, the play method should print what is happening. When it is done, play should return a result indicating whether the game ended in a pass or a not. Here is a sample output from the entire program (consisting of several games). For each game, the sequence of dice sums thrown should be shown. They are shown in parentheses in front of the final result. (Note: You will not get exactly these results. This is just to show the general appearance.) 

    What is the seed? 39228
    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.

Do not create a new pseudo-random number generator object for each throw of the die. Create and use one pseudo-random number generator object throughout, and pass it as a parameter to any function needs it. Your program should only create one random number generator object, regardless of how many games it plays, or how many times it throws the dice during a game.

Try to make the Craps class have simple methods. Do not have one big method that does everything. Think about methods that will be useful. Write a clear, precise and concise contract for each method before you write the method.

Test your program, and look at the results. Do they look reasonable? (In the long run, a player will pass about 49.3% of the time.) If you change the seed, do the results change?

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.