Computer Science 2311
Spring 2005
Laboratory Assignment 7

Handed out: 3/2/05

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 you made use of a pseudo-random number generator class called Random from the Java library.

The idea of a pseudo-random number generator is to define a function that 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₂)

There will be some maximum number N such that all of your integers r_i are less than N. You can turn r_i into a real number between 0 and 1 by dividing it by N. Define

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 Java). 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 the sequence r₁, r₂, ..., for this next function 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, since then it hardly looks random.

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

Pseudo-random number generating objects

You can create objects that generate pseudo-random numbers by creating a class. Let's call the class MyRandom. An object of class MyRandom needs to remember the current integer r_k in the sequence. Class MyRandom has a 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;
     MyRandom 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 the random number generator object works are not shown. 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.

   public int rolldie(MyRandom R)
   {
     return (int)(6*R.getnext()) + 1;
   }

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

Write a definition of a pseudo-random number generator class. Make the current integer have type long, not int, so that larger integers can be used. Here is a suggestion of the next method in that class.

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

1. Write the getnext() method. Remember to change the value that the object is remembering. Also, be sure to return a real number between 0 and 1.

2. Include a public constructor. Constructor MyRandom(seed) creates a random number generator with a given seed value.

3. Add a function rolldie that rolls one die. The version above has the random number generator passed as a parameter. Modify that so that rolldie has no parameters. It is part of the random number generator class, so it just uses the random number generator that it belongs to. How do you need to modify the rolldie method written above?

TEST YOUR CLASS. Write a main program 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?

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 methods. Encapsulate the rules of Craps in a method (or possibly a method and another helper method), so that no other method needs to know anything about those rules.

You can take a choice of (1) using static methods in the class that plays craps, and (2) creating an object that plays craps, and asking it to play. The first approach is conceptually simpler.

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.

Suggestion for writing this program. Try doing it in the following order.

1. Write the random number generator class, and write a main program to test it. Do the test. Do not continue until the random number generator class is working.

2. Write a method that plays just one game of craps. It should show the rolls of the dice, and return true if the game was a pass and false if not. Test this

3. Now write another method to play many games. This does not involve changing the method that plays one game. Instead, just use that method many times. Add reporting of the results at the end. Test it. Does the results look reasonable?

What to turn in

Turn in your final program, including both the pseudo-random number generator class and the craps playing class.