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

normal for the power computation. We check whether Theorem 9.1 is violated,
returning 0 if it is. Otherwise, we complete the power computation.

The only remaining issue is correctness. If our algorithm declares that N
is composite, then N must be composite. If N is composite, are all
witnesses? The answer, unfortunately, is no. That is, some
choices of A will trick our algorithm into declaring that N is prime. In fact, if
we choose A randomly, we have at most a 1/4 chance of failing to detect a
composite number and thus making an error. Note that this outcome is true for
any N . If it were obtained only by averaging over all N , we would not have a
good enough routine. Analogous to medical tests, our algorithm generates
false positives at most 25 percent of the time for any N .

If the algorithm
declares a number
not to be prime, it is
not prime with 100
percent certainty.
Each random
attempt has at
most a 25 percent
false positive rate.

2 ≤≤ AN 2 -

These odds do not seem very good because a 25 percent error rate gener-
ally is considered very high. However, if we independently use 20 values of
A , the chances that none of them will witness a composite number is 1/4 20 ,
which is about one in a million million. Those odds are much more reasonable
and can be made even better by using more trials. The routine isPrime , which
is also shown in Figure 9.9, uses five trials. 3

Some composites
will pass the test
and be declared
prime. A composite
is very unlikely to
pass 20 consecu-
tive independent
random tests.

summary

In this chapter we described how random numbers are generated and used.
The linear congruential generator is a good choice for simple applications, so
long as care is taken in choosing the parameters A and M . Using a uniform
random number generator, we can derive random numbers for other distribu-
tions, such as the Poisson and negative exponential distributions.
Random numbers have many uses, including the empirical study of algo-
rithms, the simulation of real-life systems, and the design of algorithms that
probabilistically avoid the worst case. We use random numbers in other parts
of this text, notably in Section 13.2 and Exercise 21.21.
This concludes Part Two of the topic. In Part Three we look at some sim-
ple applications, beginning with a discussion of games in Chapter 10 that
illustrates three important problem-solving techniques.

key concepts

false positives / false negatives Mistakes randomly made (presumably with
low probability) by some randomized algorithms that work in a fixed
amount of time. (408)

3. These bounds are typically pessimistic, and the analysis involves number theory that is
much too involved for this text.