Computer Science 2611
Spring 2000
Laboratory Assignment 6

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 called next. 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. For example, suppose that function next is defined so that next(n) = (17*n + 1) mod 23. Choose the seed to be 2. Then the sequence of numbers is

r0 = 2
r1 = next (2) = 12
r2 = next (12) = 21
r3 = next (21) = 13

So the sequence of "apparently" random numbers starts 12, 21, 13, ... (We won't use the seed as one of the pseudo-random numbers.) What is the next number in the sequence?

Different pseudo-random number generators use different functions next . One kind of functions uses next(n) = (a*n + b) mod c, where a, b and c are prime numbers, a < c and b < c.

Pseudo-random number generating objects

An object R that acts as a pseudo-random number generator has two public methods:

SetSeed: R.SetSeed(n) tells object R to set its current seed to n. R must remember n as its current value.
nextRandom: R.nextRandom() returns the next random number in the sequence. It must update the current value that R is holding, so that several calls to R.nextRandom() produce different numbers.

Suppose that a pseudo-random number generator object has class Random. Then here is a function that produces the sum of n pseudo-random numbers. It sets the seed to a chosen value (35).

   int randomSum(int n)
   {
     int k, sum;
     Random R;
     R.SetSeed(35);
     k = 0;
     sum = 0;
     while(k < n) {
       sum = sum + R.nextRandom();
       k++;
     }
     return sum;
   }

Notice that the seed is only set once, and then several pseudo-random numbers are asked for.

The assignment, part 1

Write a class of objects that are pseudo-random number generators. (This is the class Random of the example above.) Use a next function next(n) = (a*n + b) mod c, choosing numbers a, b and c to be fairly large prime numbers. Keep them less than 32,000, or there will be problems with arithmetic overflow. Be sure that a, b and c are different prime numbers, or your pseudo-random number generator will produce poor results.

Each object should hold a value that is its current value . Each object should have a function SetSeed that sets the current value to a particular value, and a function nextRandom that changes the current value to the next value in the pseudo-random sequence, and returns that next value. Each call to nextRandom should produce an different number.

Write a main program to test the pseudo-random number generator. Just have it print the first 20 numbers generated, after setting the seed. Do the numbers look reasonable? Do not move on to part 2 until you have a working pseudo-random number generator class.

Hints

Draw a picture of a pseudo-random number generator object. What variable(s) does it need? What public methods does it have?

Note that the constants a, b and c are not variables, they are constants. They are only used in one place, the next function. So build them into the next function, not into the object. You can declare a constant using the keyword const. For example, to declare constant b (of type long) to be 917, use

    const long b = 917;

To test whether a number is prime, you can just run a program. For your benefit, here is a function that will tell whether a number is prime. It will help you to choose reasonable values for a, b and c.

   bool isPrime(long n)
   {
     if(n < 2) return 0;

     long k = 2;
     while(k*k <= n) {
       if(n % k == 0) return 0;
       k++;
     }
     return 1;
   }

Assignment part 2: Using the random number generator

Two numbers are relatively prime if their greatest common divisor is 1. Suppose you choose two integers between 1 and N at random. What is the probability that they are relatively prime? As N gets large, that probability approaches 6/(pi*pi), where pi = 3.14159265... So one way to estimate pi is to select pairs of numbers at random from a large range, and to keep track of the fraction of the pairs that consist of two relatively prime numbers.

Write a main program that reads two integers K and S. It should create a random number generator object, set the object's seed to S, and then get K pairs of random numbers. (That is a total of 2K random numbers.) It should then print an estimate of pi based on the number of pairs that were relatively prime. Show the estimate to five decimal places.

Test your program. If your answer is consistently 3.00000 or 3.16228 or 3.31662 there is something wrong with your program. 3.16228 is about the square root of 10, and 3.31662 is about the square root of 11. This indicates that you are using integer arithmetic where you need to use real arithmetic.

What to turn in

Turn in a printout of your solution to the second part. Be sure that it is well commented.