Randomization - Data Structures and Problem Solving Using Java - page 394

One important application of random numbers is in program testing. Sup-
pose, for example, that we want to test whether a sorting algorithm written in
Chapter 8 actually works. Of course, we could provide some small amount of
input, but if we want to test the algorithms for the large data sets they were
designed for, we need lots of input. Providing sorted data as input tests one
case, but more convincing tests would be preferable. For instance, we would
want to test the program by perhaps running 5,000 sorts for inputs of size
1,000. To do so requires writing a routine to generate the test data, which in
turn requires the use of random numbers.

Random numbers
have many impor-
tant uses, including
cryptography, simu-
lation, and program
testing.

Once we have the random number inputs, how do we know whether the
sorting algorithm works? One test is to determine whether the sort arranged
the array in nondecreasing order. Clearly, we can run this test in a linear-time
sequential scan. But how do we know that the items present after the sort are
the same as those prior to the sort? One method is to fix the items in an
arrangement of 1, 2, ..., N . In other words, we start with a random permutation
of the first N integers. A permutation of 1, 2, ..., N is a sequence of N integers
that includes each of 1, 2, ..., N exactly once. Then, no matter what permuta-
tion we start with, the result of the sort will be the sequence 1, 2, ..., N , which
is also easily tested.
In addition to helping us generate test data to verify program correctness,
random numbers are useful in comparing the performance of various algo-
rithms. The reason is that, once again, they can be used to provide a large
number of inputs.
Another use of random numbers is in simulations. If we want to know the
average time required for a service system (for example, teller service in a bank)
to process a sequence of requests, we can model the system on a computer. In this
computer simulation we generate the request sequence with random numbers.
Still another use of random numbers is in the general technique called the
randomized algorithm , wherein a random number is used to determine the
next step performed in the algorithm. The most common type of randomized
algorithm involves selecting from among several possible alternatives that are
more or less indistinguishable. For instance, in a commercial computer chess
program, the computer generally chooses its first move randomly rather than
playing deterministically (i.e., rather than always playing the same move). In
this chapter we look at several problems that can be solved more efficiently by
using a randomized algorithm.

A permutation of
1, 2, ..., N is a
sequence of N inte-
gers that includes
each of 1, 2, ..., N
exactly once.

random number generators

9.2

How are random numbers generated? True randomness is impossible to
achieve on a computer, because any numbers obtained depend on the algorithm