## Random Number Generators

So you are sitting in class, enjoying a worksheet of problems when Mrs. Krupnick says, "OK class, let's play a game. I need someone to pick a number from 1 to 100." It was an unusual day, everyone seemed to be really involved with their own work and only one hand went up. It was John Doe's hand, and when everyone looked around and saw that, there was a big groan coming from the class. The reason for this is that everyone knows that when John is asked this question, he always answers the same way - "I pick the number one", he always says. Even Mrs. Krupnick knows this, so she really doesn't want to pick John. To make the game fun it needs to work for any number, not just something that can be predicted.

One way for Mrs. Krupnick to get out of this difficulty is to turn to the computer and ask the computer to give her a random number, that is, a number which can not be predicted. Now she knows that the computer can not really do this (it's the nature of a computer... if you knew what the computer knows, you could correctly predict what number the computer will give) but it can do a pretty good job of "faking it". The program the computer uses to produce such numbers is called a Random Number Generator. We shall see how you can use a LFSR to make a random number generator.

Even though modern computers seem to be able to "read your mind" and do what you want them to do, they really can't. You have to be very careful to tell a computer exactly what you want it to do. Even after you have given the computer all the information you think it needs to know, it might still need to know something that you didn't think to tell it. This is what happens with a random number generator. When you want it to pick a "random" number, it needs to know the biggest and the smallest number that are acceptable to you (this is called the "range of values") and it also needs to know if you want the numbers it produces to be repeatable or not. This second need is a little strange, it means that if you restart the program at some later time you can get the same sequence of "random" numbers in the same order. This doesn't seem to be very random behavior, but it is often desirable when you are trying to work out the bugs in some other program you are creating that uses the random number generator. At other times (say, when all the bugs are worked out of a program) you might not want this kind of behavior and would like to have the random number generator act more "random", so that you could not predict what will come out of the program, and if the program is restarted it will not repeat itself. When you want the random number generator to be repeatable, you have to supply it with a seed (for the LFSR that it will use). To get the same sequence of "random" numbers at a different time, you need to give it the same seed again. Computer programmers use a clever "trick" to tell the computer when you don't want this repeatable behavior. Remember that the number 0 is not a seed for a LFSR, so we can use this number to mean something different than a seed. Thus, we will give the random number generator three numbers as input, the first two are the range of values (the smallest number we want and the largest number we want) while the third number must range between 0 and the maximum possible seed for the LFSR. If this third number is 0, the program will act in its random manner while if the number is not 0 the program will use the number as a seed for the LFSR and act in its repeatable mode.

In a computer program (a listing of commands for the computer) when you want random numbers to be produced by the computer, there will be a statement that looks something like RANDOMIZE(10,50,77). This is asking the computer to produce "random" numbers from 10 to 50 in the repeatable mode with seed 77. On the other hand RANDOMIZE(1,100,0) would be asking for "random" numbers from 1 to 100 in the non-repeatable mode. This command statement sets up the random number generator and there will be another command which asks for the next output from this random number generator.

Now lets see how the random number generator works. First of all, there is a LFSR available to be used which is on a microchip. The LFSR should have at least 16 registers and be designed to produce a sequence with the longest possible period, i.e. 216-1 = 65,536 - 1 = 65,535 if there are 16 registers. If the third number that is given to the program is not 0, then it (written in binary) is used as the seed of the LFSR. On the other hand, if this number is 0, we need to find a seed in some other way. Usually, the program looks into computer memory in a place where it is known that the entries are rapidly changing, such as the place where the computer stores the time, to find a seed. Using the fastest changing part of the stored time (the milliseconds) the program fills the registers with this seed. If you were to run the program again in this way, it is very, very unlikely that you would get the same seed again. Now that the LFSR has been seeded, there is one other thing that must be done before the random number generator can generate random numbers. Subtract the lowest acceptable value from the highest acceptable value. This number is the spread of the range. Then find the largest power of two which is less than or equal to the spread, and write this number as 2 raised to a power. We want to know this power. Let's call it P (standing for power). So, if we set up our random number generator with the command RANDOMIZE(10,50,77), we would seed the LFSR with 77 (written in binary) and then calculate 50 - 10 = 40. The biggest power of 2 less than or equal to 40 is 32 which is 25, so P = 5. With the other command, RANDOMIZE(1,100,0), the LFSR would be seeded by looking at the internal clock and we calculate 100 - 1 = 99. The largest power of 2 here is 64 = 26, so P = 6.

Find the value for P for each of the following commands:

1. RANDOMIZE(1,10,65500)
2. RANDOMIZE(10,150,0)
3. RANDOMIZE(0,260,7117)

Now we are ready to produce random numbers. After everything has be set up with the RANDOMIZE(*,*,*) command, when asked for a random number the random number generator will run the LFSR P+1 times to get a base 2 number with P+1 positions. If the number is less than or equal to the spread then the smaller acceptable value is added to it and this result is the random number. If, on the other hand, the base 2 number is too large, it is just thrown away and the LFSR is run for another P+1 times to get a new number, and this will be repeated until the base 2 number is small enough. So, consider this example: let the command RANDOMIZE(1,10,5) be used to set up the random number generator. The spread is 10-1 = 9 and the value of P is 3. When asked for a random number, the LFSR is run 4 times giving the output (1010)2 = 1(8) + 0(4) + 1(2) + 0(0) = 10. As this is bigger than the spread (= 9), the LFSR is run 4 more times and the output might look like (0110)2 = 0(8) + 1(4) + 1(2) + 0(0) = 6. Since this is less than 9, it is acceptable and the random number generator gives us the value of 7 = 6 + 1. With another request for a random number, we might get an output from the LFSR such as (0000)2 = 0 and the random number we get will be 1 = 0 + 1.

Suppose that a random number generator is set up with the command RANDOMIZE(10,50,0) and the output of the LFSR will start off as
1000100110011101100011010001110010010011011100110001 ...

1. What is the first random number produced ?
2. What is the second random number?
3. What is the third?