Random Numbers

Random Numbers on a computer are not really random. They are a sequence of "pseudo" random numbers.

Random Numbers on a Computer

First off, it is not really possible (nor desirable) to have real random numbers. What we want is a repeatable sequence of seemingly random numbers that satisfy certain properties, such as the average value of a list of random numbers between say, 0 and 1000, should be 500. Other properties, such as no (predictable) relation between the current random number and the next random number is desireable.

In any program where random values are necessary (for example, most simulations) the programming language must provide us with a random number generator. This will be a function that will, when called, provide us with a single random number... when called again, provide us with another random number.

"Pseudo" random number sequences

Generating a single random number is easy. 27. There!

Generating a sequence of random numbers is quite difficult because we want certain assumptions about this sequence to be true!

Note that "Random" number generators produce what are called "pseudo" random numbers, meaning that the numbers only "approximate" real randomness.

Some Goals:

1. Repeatable: Why?
2. Speed (Fast to Compute): Why?
3. Average value is average of range.
4. Odd followed by an Even as Likely as Even followed by an Odd.
5. When choosing 1000 numbers between 0 and 1000 we will not hit every number.
6. When choosing a numbers between 0 and 1000 we are equally likely to get any number.
7. When choosing 10000 numbers between 0 and 1000 we are likely to get roughly 10 of each number.

Some Possible Techniques to Create Random Sequence:

1. Time - Use the computers clock
2. Radiation - Install some radiation in the computer and compute how often the atoms decay... (uggh)
3. Math - use a formula (see below)

The advantage of using mathematics to generate a random number (sequence) is that it is REPEATABLE. This is important for the following reason: debugging a program. Imagine the problems you already have finding errors in your code. What would happen if the "path" (or program flow) was different (random) every time? Debugging would be a nightmare! At the end of the day, the programmer wants the same sequence of random numbers every time, but the user may require a different sequence. To generate a different sequence of random numbers we use a "seeding" function. For the purposes of this course, you will most likley not need to "seed" your random number generator.

Language Specific Functions.

In the case of Matlab and C, this generator is the "rand()" function. In the case of Java or Actionscript there is a random function associated with the Math library.

	    
	      fifty_fifty_decision = (rand() > .5);
	    
	  

	    
	      #include <stdlib>

	      ...
	      
	      float between_0_and_1;
	      bool  fifty_fifty_decision;

	      between_0_and_1 = rand() / RAND_MAX;
	      
	      fifty_fifty_decision = (between_0_and_1 > .5);
	    
	  

	    
	      var fifty_fifty_decision:Boolean = (Math.random() > .5);
	    
	  

	    
	      var random_number:int  = Math.ceil((Math.random() * 10));
	    
	  

Examples

Below are examples of generating values using the random number generator.

For conciseness, these notes use a rand function that computes a random number between 0 and (less than) 1. If the function you are using does not produce a number between 0 and 1, you should be able to convert your number generator to this format by dividing by a large integer.

Given a random number between 0 and 1, it is relatively easy to generate random numbers or values of any type. For example:

• A Random number between 0 and 100

  	    value = rand() * 100;
  	  

• A Random true or false

  	    decision = (rand() > .5);
  	  

• A Random number between 50 and 100

  	    x = (rand() * 50) + 50;
  	  

• A Random integer between 1 and 10

  To get an integer from a floating point value we can use functions such as round or ceil or floor. The round function returns the nearest integer, ceil the next higher integer, and floor, the next lower integer. Thus ceil of 1.001 is 2 and ceil of 1.999 is also 2. round of 1.001 is 1 and round of 1.999 is 2. The Floor of 1.999 is 1, etc. The ceil of 1.9 is 2, as is the ceil of 1.1 or 1.0001.

  	    x = ceil(rand() * 10);
  	  

Random Number Generation

It is unlikely that you will ever have to write your own random number generator. Most/all languages you will ever use will already have one written for you. That being said, there is some value in knowing some possible ways that numbers are generated. This value lies in knowing what to expect when you get a sequence of random numbers... You wouldn't want your Pac-Man ghosts to always drift toward the upper right of the screen, which could happen of the random numbers they used to move were not so random...

The following idea is simple, fast, effective random number generator, but one very sensitive to the choice of constants:

next_number = (previous_number * Constant1) Mod Constant2

We don't really need a next and previous variables, so we can say:

number = (number * Constant1) Mod Constant2

Constant2 is usually chosen as a prime. Why? (think next_number = 0)

Problem: Overflow!

Solution: More Math!

	  A = Constant 1;
          M = Constant 2;

	  Q = M / A;
          R = M % A;

          number = ( A * (number mod Q)    ) -
                   ( R * floor(number / Q) );

	  if (number is negative)
            number = number + M;
          end
      

The idea of the above code is to avoid overflow by rearranging the equation such that no part can ever be bigger than M.