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

Finally, the Random class provides a generator for nonuniform random
numbers when they are required. In Section 9.3 we provide the implementa-
tion for the methods nextPoisson and nextNegExp .
It may seem that we can get a better random number generator by adding
a constant to the equation. For instance, we might conclude that

X i = ( 48,271 X i + 1 ) mod 2 31 ( - 1 )

+ 1

would somehow be more random. However, when we use this equation, we
see that

179,424,105 + 1) mod (2 31 - 1) = 179,424,105 (48,271 ⋅

Hence, if the seed is 179,424,105, the generator gets stuck in a cycle of period 1,
illustrating how fragile these generators are.
You might be tempted to assume that all machines have a random number
generator at least as good as the one shown in Figure 9.2. Sadly, that is not the
case. Many libraries have generators based on the function

X i = ( AX i + C ) mod 2 B

+ 1

where B is chosen to match the number of bits in the machine's integer, and
C is odd. These libraries, like the nextInt routine in Figure 9.2, also return
the newly computed state directly, instead of (for example) a value between
0 and 1. Unfortunately, these generators always produce values of that
alternate between even and odd—obviously an undesirable property.
Indeed, the lower k bits cycle with a period of (at best). Many other ran-
dom number generators have much smaller cycles than the one we provided.
These generators are not suitable for any application requiring long
sequences of random numbers. The Java library has a generator of this form.
However, it uses a 48-bit linear congruential generator and returns only the
high 32 bits, thus avoiding the cycling problem in lower-order bits. The con-
stants are A = 25,214,903,917, B = 48, and C = 11.
This generator is also the basis for drand48 used in the C and C++ librar-
ies. Because Java provides 64-bit longs, implementing a basic 48-bit ran-
dom number generator in standard Java can be illustrated in only a page of
code. It is somewhat slower than the 31-bit random number generator, but
not much so and yields a significantly longer period. Figure 9.3 shows a
respectable implementation of this random number generator.
Lines 10-13 show the basic constants of the random number generator.
Because M is a power of 2, we can use bitwise operators (see Appendix C
for more information on the bitwise operators). M =

X i

2 k

2 B can be computed