Painting Random Colors
A Visual Approach to Random Number Generation
Author: Samuel V. Niles
Web site: http://www.samniles.com/sam/
Date: January 26, 2004
Introduction
Randomness is a powerful phenomenon, yet we often take it for granted. Perhaps this is because of its apparent simplicity, and ubiquity. If we need a random result, then we simply flip a coin, roll a pair of dice, or shuffle a deck of cards. Randomness is everywhere, right? Wrong.
A computer processor is one place where there is no randomness, yet it is a place where randomness is most needed, in applications ranging from games to secure communications. So, where do these software applications get their random behavior? Software developers must program random behavior into their applications. They typically use a special mathematical algorithm to generate a series of numbers which appears random (pseudorandom numbers). These numbers are then translated into meaningful results, like heads or tails.
This paper describes the Multiplicative Congruential Method, which is one of the most common methods of pseudorandom number generation. Despite its imposing name, this method is actually quite simple, and it is defined using elementary algebra. Rather than overwhelming readers with reams of numbers, this paper takes a visual approach to randonmess, translating numbers into color-coded images. Just glancing at these images, readers can quickly observe the presence - or absence - of pattern, which is the very definition of randomness.
While browsing this document in Microsoft Internet Explorer, readers can generate their own randomly-colored images at the click of a button using the Interactive Random Color Generator, which is included in the Appendix.
Visualizing Randomness
Observe the image on the left. It is a large square comprised of sixty-four
small squares, each colored black or white, with no apparent pattern. Would you
believe that these colors were selected by flipping a coin sixty-four
times? Well, don't believe it. While I certainly hope the pattern looks random,
I did not actually flip coins to create it. Instead, I used my computer to
apply the Multiplicative Congruential Method of pseudorandom number generation.
I generated 64 pseudorandom numbers (one for each small square) ranging from 1
to 1,020,378. Numbers from 1 to 510,189 indicated a black square, and numbers
from 510,190 to 1,020,378 indicated a white square.
Multiplicative Congruential Method
Definition.
To generate N pseudorandom integers X =
(X1, X2,
X3, ..., XN)
on the interval {1, 2, ..., (M-1)}:
(a) Choose M (the Modulus), a large prime number.
(b) Choose A (the Multiplier), a positive integer not equal to M, 2M, 3M,
...
(c) Choose X0 (the Seed) from {1,
2, ..., (M-1)}.
(d) For i = 1, 2, ..., N calculate
Xi = (AX(i-1))
Mod M.
Uniformly Distributed Random Numbers.
Given N pseudorandom integers X =
(X1, X2,
X3, ..., XN)
randomly distributed on the interval {1, 2, ..., (M-1)},
real numbers, U, are uniformly distributed on [0, 1) where:
Ui = (X(i)
- 1) / (M(i) - 1).
Example: Flipping Coins. Let's suppose we want to flip a dozen virtual coins. First, we need to generate a series of 12 pseudorandom integers. To keep the numbers down to a manageable size (so readers don't need their calculators), we have selected small values for our parameters: N = 12; M = 7; A = 24; and X0 = 1. The table below illustrates each step in the algorithm, including intermediate steps in algebraic calculation defined above. Notice the application of modular arithmetic to obtain column (4) from column (3). Also, notice how the numerical results (1, 2, 3) or (4, 5, 6) are translated into "Tails" or "Heads," respectively.
| Results - Flipping Coins | ||||||
| (1) | (3) | (3) | (4) | (5) | (6) | (7) |
| i | X(i-1) | AX(i-1) | X(i) | U(i) | D(i) | R(i) |
| 1 | 1 | 24 | 3 | 0.3333 | 0 | Tails |
| 2 | 3 | 72 | 2 | 0.1677 | 0 | Tails |
| 3 | 2 | 48 | 6 | 0.8333 | 1 | Heads |
| 4 | 6 | 144 | 4 | 0.5000 | 1 | Heads |
| 5 | 4 | 96 | 5 | 0.6667 | 1 | Heads |
| 6 | 5 | 120 | 1 | 0.0000 | 0 | Tails |
| 7 | 1 | 24 | 3 | 0.3333 | 0 | Tails |
| 8 | 3 | 72 | 2 | 0.1677 | 0 | Tails |
| 9 | 2 | 48 | 6 | 0.8333 | 1 | Heads |
| 10 | 6 | 144 | 4 | 0.5000 | 1 | Heads |
| 11 | 4 | 96 | 5 | 0.6667 | 1 | Heads |
| 12 | 5 | 120 | 1 | 0.0000 | 1 | Tails |
Warning. Don't use these results at home, or at work! While this example illustrates the simplicity of the Multiplicative Congruential Method, it also illustrates one of the potential pitfalls of the method - repetition. Notice the pattern which repeats every 6, or (M-1), iterations. This is obviously not a good property for a series of supposedly-random numbers. So, we should simply choose larger values for M and A, right? Yes, that would help, however larger values still do not guarantee the absence of repetition. As illustrated in this example, repetition will always occur when the number of trials, N, exceeds the Modulus, M. However, less obvious is the fact that this type of repetition can also occur before the Mth trial. Whether this unfortunate event occurs depends on the specific values of M and N. Any series of numbers generated with this method should be check for repetition.
Summary
Some of our most cherished computer applications rely on the phenomenon of randomness. Randomness is such a simple concept, yet it is also powerful, and elusive. When you really need randomness, it is actually quite hard to find. In the case of a computer, its impossible to find. The Multiplicative Congruential Method is an appealing and simple solution, however we should remember that it is merely an approximation of true randomness. Any results should be checked for repetition, which threatens to defeat the entire purpose of this method.
Exercises
Exercise 1 (Repeat at trial number M).
N = 64
M = 7
A = 24
X0 = 1
This exercise uses the same parameters as the coin-flipping example dicussed
above.
Enter these parameters in the form below, click the Generate Colors button, and
confirm that the results are equivalent.
This exercise illustrates an important feature of the Multiplicative
Congruential Method.
This method is functional, in the strict mathematical meaning of the word.
If you ask it the same question (that is, if you input the same parameters),
then you will get the
same answer, every time.
This can be an extremely helpful feature, as two people can run the same
program and
obtain the same results.
On the other hand,
if we want our application to have different results for different users,
then we must explicitly program that behavior,
perhaps using Social Security Number to create a user-specific seed.
Exercise 2 (Repeat at trial number (M-1)/2).
N = 64
M = 7
A = 23
X0 = 1
This exercise shows how repetition can occur even for iterations i < (M-1). Note how the X's get stuck in a pattern, repeating (2, 4, 1, 2, 4, 1, ...). Try X0 = 2, or 4. Notice how the X's gut stuck in the same pattern. What happens when X0 = 3? Repetition like this can occur even when parameters M and A are very large. For this reason, it is important to check all results for repetition.
Exercise 3 (Recommended Parameters).
N = 64
M = 2,147,483,647 = 2^31 - 1
A = 16,807 = 7^5
X0 = 982,451,653 (the 50,000,000th
prime number)
The above values for parameters M and A are suggested in [Simulation, by Sheldon M. Ross], as having optimal performance on computers with a 32-bit processor. Note in the formula for M, that 2 is raised to the power of 31; the remaining 1 bit is reserved for the + or - sign. If you are a programmer, you may recognize 2,147,483,647 as the largest possible value which can be stored in a Long Integer variable. Now, you know where that number comes from!
Exercise 4 (32-bit integers).
N = 64
M = 1,020,379 (the 80,000th prime number)
A = 10,570,841 (the 700,000th prime number)
X0 = 978,479
Property:
For each iteration (n = 1, 2, ..., N) the virtual roulette wheel (M) will
spin at least 10 times.
Proof: Since integer X(i) >= 1,
and integer A > > 10(M),
AX(i) > 10(M).
Note that the seed for this example, 978,479, equals X(320),
where X(0) = 1.
In other words, start with a seed equal to 1, then generate 5 sets of 64
numbers.
The seed for the 6th iteration will be 978,479.
Resources
Book Title: Simulation
Author: Sheldon M. Ross
Publisher: Elsevier Science &
Technology
Date: 2002
Description: A textbook on
computerized Monte Carlo simulation.
Chapter 3, Random Numbers, presents the Multiplicative Congruential Method
Book Title: The Code Book: The
Science of Secrecy
from Ancient Egypt to Quantum Cryptography
Author: Simon Singh
Publisher: Knopf Publishing Group
Date: 2000
Description: A history of
codemaking and codebreaking.
See pages 122-124 for a discussion of randomly-generated encryption keys.
Web Page:
Random Number Generators - Literature
URL: http://random.mat.sbg.ac.at/literature/
Description: The latest academic
literature on Random Number Generators, as well as similar information on the
statistics specialty of stochastic analysis.
Web Page:
The Nth Prime Page
URL: http://primes.utm.edu/nthprime/
Description: A usuful place to
find very large prime numbers
(to use as parameters for a pseudorandom number generator).
Web Page:
The 10,000 Smallest Primes
URL: http://www.math.utah.edu/%7Ealfeld/math/p10000.html
Description: The 10,000 smallest
prime numbers.
Interactive Random Color Generator
Input Parameters
Random Colors
| M = | 0 |
| A = | 0 |
| X0 = | 0 |
| Colors: | 0 |
Calculation Details
| i | AX(i-1) | Xi | Di |
| 1 | |||
| 2 | |||
| 3 | |||
| 4 | |||
| 5 | |||
| 6 | |||
| 7 | |||
| 8 | |||
| 9 | |||
| 10 | |||
| 11 | |||
| 12 | |||
| 13 | |||
| 14 | |||
| 15 | |||
| 16 | |||
| 17 | |||
| 18 | |||
| 19 | |||
| 20 | |||
| 21 | |||
| 22 | |||
| 23 | |||
| 24 | |||
| 25 | |||
| 26 | |||
| 27 | |||
| 28 | |||
| 29 | |||
| 30 | |||
| 31 | |||
| 32 | |||
| 33 | |||
| 34 | |||
| 35 | |||
| 36 | |||
| 37 | |||
| 38 | |||
| 39 | |||
| 40 | |||
| 41 | |||
| 42 | |||
| 43 | |||
| 44 | |||
| 45 | |||
| 46 | |||
| 47 | |||
| 48 | |||
| 49 | |||
| 50 | |||
| 51 | |||
| 52 | |||
| 53 | |||
| 54 | |||
| 55 | |||
| 56 | |||
| 57 | |||
| 58 | |||
| 99 | |||
| 60 | |||
| 61 | |||
| 62 | |||
| 63 | |||
| 64 |