Java Reference
In-Depth Information
Our numbers do not satisfy these properties. Consecutive numbers always
sum to an odd number, and our sequence is duplicate-free. We say then that
our simple pseudorandom number generator has failed two statistical tests.
All pseudorandom number generators fail some statistical tests, but the good
generators fail fewer tests than the bad ones. (See Exercise 9.16 for a common
statistical test.)
In this section we describe the simplest uniform generator that passes a
reasonable number of statistical tests. By no means is it the best generator.
However, it is suitable for use in applications wherein a good approximation
to a random sequence is acceptable. The method used is the linear congruen-
tial generator, which was first described in 1951. The
linear congruential gen-
erator
is a good algorithm for generating uniform distributions. It is a random
number generator in which numbers
The
linear congru-
ential generator
is a
good algorithm for
generating uniform
distributions.
X
1
,
X
2
,
…
are generated that satisfy
X
i
=
AX
i
mod
M
(
)
(9.1)
+
1
Equation 9.1 states that we can get the th number by multiplying the
i
th number by some constant
A
and computing the remainder when the result
is divided by
M
. In Java we would have
(
i
+
1
)
x[ i + 1 ] = A * x[ i ] % M
We specify the constants
A
and
M
shortly. Note that all generated numbers will be
smaller than
M
. Some value must be given to start the sequence. This initial
value of the random number generator is the
seed.
If , the sequence is not
random because it generates all zeros. But if
A
and
M
are carefully chosen, any
other seed satisfying
The
seed
is the ini-
tial value of the
random number
generator.
X
0
X
0
=
0
1
≤
X
0
<
M
is equally valid. If
M
is prime,
X
i
is never 0. For
example, if
M
=
11
,
A
=
7
, and the seed
X
0
=
1
, the numbers generated are
The length of a
sequence until a
number is repeated
is called its
period
.
A random number
generator with
period
P
generates
the same sequence
of numbers after
P
iterations.
7, 5, 2, 3, 10, 4, 6, 9, 8, 1, 7, 5, 2, ...
(9.2)
Generating a number a second time results in a repeating sequence. In our
case the sequence repeats after numbers. The length of a
sequence until a number is repeated is called the
period
of the sequence. The
period obtained with this choice of
A
is clearly as good as possible because all
nonzero numbers smaller than
M
are generated. (We must have a repeated
number generated on the 11th iteration.)
If
M
is prime, several choices of
A
give a full period of , and this
type of random number generator is called a
full-period linear congruential
generator.
Some choices of
A
do not give a full period. For instance, if
and
M
-
1
=
10
M
-
1
A
full-period linear
congruential gener-
ator
has period
M
- 1
.
A
=
5
X
0
=
1
, the sequence has a short period of 5:
5, 3, 4, 9, 1, 5, 3, 4, ...
(9.3)
Search WWH ::
Custom Search