Java Reference
In-Depth Information
We obtained this closed form solution again by applying the Master Theorem.
Unfortunately, while Strassen's algorithm does in fact reduce the asymptotic
complexity over the standard algorithm, the cost of the large number of addition
and subtraction operations raises the constant factor involved considerably. This
means that an extremely large array size is required to make Strassen's algorithm
practical in real applications.
16.3.4
Random Numbers
The success of randomized algorithms such as were presented in Section 16.2 de-
pend on having access to a good random number generator. While modern compil-
ers are likely to include a random number generator that is good enough for most
purposes, it is helpful to understand how they work, and to even be able to construct
your own in case you don't trust the one provided. This is easy to do.
First, let us consider what a random sequence. From the following list, which
appears to be a sequence of “random” numbers?
• 1, 1, 1, 1, 1, 1, 1, 1, 1, ...
• 1, 2, 3, 4, 5, 6, 7, 8, 9, ...
• 2, 7, 1, 8, 2, 8, 1, 8, 2, ...
In fact, all three happen to be the beginning of a some sequence in which one
could continue the pattern to generate more values (in case you do not recognize
it, the third one is the initial digits of the irrational constant e). Viewed as a series
of digits, ideally every possible sequence has equal probability of being generated
(even the three sequences above). In fact, definitions of randomness generally have
features such as:
• One cannot predict the next item. The series is unpredictable.
• The series cannot be described more briefly than simply listing it out. This is
the equidistribution property.
There is no such thing as a random number sequence, only “random enough”
sequences. A sequence is pseudorandom if no future term can be predicted in
polynomial time, given all past terms.
Most computer systems use a deterministic algorithm to select pseudorandom
numbers. 1 The most commonly used approach historically is known as the Linear
Congruential Method (LCM). The LCM method is quite simple. We begin by
picking a seed that we will call r(1). Then, we can compute successive terms as
follows.
r(i) = (r(i 1) b) mod t
where b and t are constants.
1 Another approach is based on using a computer chip that generates random numbers resulting
from “thermal noise” in the system. Time will tell if this approach replaces deterministic approaches.
Search WWH ::




Custom Search