Computer Science 2611
Summer 1999
Laboratory Assignment 8

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
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, b and c are prime numbers, a < c and b < c.

The assignment, part 1

Write a class of objects that are pseudo-random number generators. 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. 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.

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

Turn in a printout of your solution to the second part.