Computer Science 2611
Summer 2000
Laboratory Assignment 6

Pseudo-random number generators

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)

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

Different pseudo-random number generators use different functions next . One kind of functions 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.

Pseudo-random number generating objects

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. It just replaces the current value of R by the next value in the sequence, and returns that new value.

Suppose that a class Random is created for pseudo-random number generator objects. Then here is a function that produces the sum of 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. It sets the initial seed to 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;
   }

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. Notice that, since the random number generator is an object, it is passed by reference.

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

The assignment, part 1

Each object should hold a value that is its current value . Make the variable(s) in the object private. 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

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

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. The result should be close to 6/pi². How can you estimate pi from your result?

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, since you need two random numbers for each test.) 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. Be careful with your arithmetic. Remember that the quotient of two integers is always forced to be an integer. If your answer is consistently 3.00000 or 3.16228 or 3.31662 there is something wrong with your program. 3.00000 is the square root of 9, 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