8.4 Home-Made Random Numbers

We've already used Turing's built-in random number generator. Now we're going to take a closer look at how to write our own random number generator. It will give us an idea of how random numbers can be generated by a computer.

We are going to be using mathematical methods to produce sequences of numbers that appear to be random. In actual fact the sequence of numbers can be predicted but to a user they will appear random. They are known as pseudo-random numbers. The method we will use is called the linear-conguential method. For this method we start with some integer, called a seed, and then keep applying this formula

seed := (MULTIPLIER * seed + INCREMENT) mod MODULUS
MULTIPLIER, INCREMENT and MODULUS are constants. If you choose appropriate values for these constants then the successive values of seed will be randomly distributed over the range 0 <= seed < MODULUS. Suppose that we had the constants defined as MULTIPLIER = 5, INCREMENT = 3 and MODULUS = 8 and that seed had a starting value of 2. If we use the formula here are the next values of seed that we will obtain. 
  1. seed = (5 * 2 + 3) mod 8
     = 13 mod 8
     = 5 
  2. seed = (5 * 5 + 3) mod 8
     = 28 mod 8
     = 4 
  3. seed = (5 * 4 + 3) mod 8
     = 23 mod 8
     = 7 
  4. seed = (5 * 7 + 3) mod 8
     = 38 mod 8
     = 6
Eventually we will produce the original value of seed and then the sequence will repeat. Since we want these numbers to appear random this seems to be a serious problem. If we choose better constants than the previous example so that the repetition does not happen for a long time the sequence will appear random. One good choice of constants is MULTIPLIER = 6293, INCREMENT = 997 and MODULUS = 163848

Let's look at a making our own random function using this approach. Here is the code. 

function random (var seed : int) : real
   const MULTIPLIER := 6293
   const INCREMENT := 997
   const MODULUS := 163848
   
   seed := (MULTIPLIER * seed + INCREMENT) mod MODULUS
   result seed / MODULUS
end random

Notice that we are making our random function produce a real number less than 1 and greater than or equal to 0. This makes it easier to use our function and to get a random number in any range we wish. Otherwise we'd get a number less than 163848 (MODULUS) and greater than or equal to 0.

So let's start using our function. Suppose we had the following declarations: 

var seed : int := 10
var die, seed : int

To simulate rolling a single 6-sided die we would need a random number in the range {1, 2, 3, 4, 5, 6}. Here is a statement that uses our function and sets the variable die to a number from that set: 

die := floor(random(seed) * 6) + 1
To make the variable card equal to a random number in the set {1, 2, 3, .. 52} we would say: 
card := floor(random(seed) * 52) + 1
Here is a program that picks 10 random numbers between 100 and 200 (inclusive) and prints them: 

var seed : int := 25

function random (var seed : int) : real
   const MULTIPLIER := 6293
   const INCREMENT := 997
   const MODULUS := 163848
   
   seed := (MULTIPLIER * seed + INCREMENT) mod MODULUS
   result seed / MODULUS
end random

for i : 1 .. 10
   put floor(random(seed) * 101) + 100
end for

It will produce the following output: 
197
177
127
155
138
128
190
193
156
173

Notice I said it will produce the following output. Every time you run this program you will get the same output. Try changing the intial value of seed and see what happens. It we change seed to 12345 we get this output: 
114
178
199
172
151
137
138
107
104
133

The random function always generates the same sequence of numbers if you start with the same seed value. To make things more random, replace the first line in the program with this statement: 

var seed : int := Time.Sec mod 1000
The statement Time.Sec calls a function that returns the number of seconds since January 1, 1970. We mod it with 1000 so the number won't be too big for our random function. This way our starting seed is unpredictable. When you are testing a program with random values it is convenient to be able to specify a specific value for seed. That way you get the same results every time and it is easier to fix bugs. When your program is complete then you can use Time.Sec to get really random results.


Exercise 8.4

  1. Continue the process of generating numbers using the values shown in the first example until six more values have been produced. By examining these, can you predict the next ten values?

    1. Give the first six values that will be generated by using a random number generator like the one shown in the first example, using the following values.

      i. modulus = 16
   multiplier = 3
   increment = 4
   seed = 2
      ii. modulus = 16
    multiplier = 9
    increment = 7
    seed = 2
      iii. modulus = 16
     multiplier = 8
     increment = 1
     seed = 2

    2. Compare the results obtained in part (a). Which set of values gives the best results? Justify your answer.

  3. If the value of modulus is 100, how many values can be generated before a repetition is certain to occur?

  4. Assuming that a call to random(seed) produces a random real value that is equal to or greater than zero and less than one, write a statement that will make the int variable result take on a random value uniformly distributed over the given set.
    1. {1, 2, 3, ..., 10}
    2. {1, 2, 3, ..., 52}
    3. {5, 10, 15, ..., 100}
    4. {-5, -4, -3, ..., 5}
    5. {100, 110, 120, ..., 300}

    1. Write a complete program, using your home-made random number generator, that simulates one thousand throws of a pair of regular six-sided dice and produces a table showing the frequency with which each possible sum appears.
    2. From the results of your program, which sum do you think is most likely to come up when two dice are rolled?