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

If we choose M to be a 31-bit prime, the period should be significantly
large for many applications. The 31-bit prime = 2,147,483,647
is a common choice. For this prime, A = 48,271 is one of the many values that
gives a full-period linear congruential generator. Its use has been well studied
and is recommended by experts in the field. As we show later in the chapter,
tinkering with random number generators usually means breaking, so you are
well advised to stick with this formula until told otherwise.
Implementing this routine seems simple enough. If state represents the
last value computed by the nextInt routine, the new value of state should be
given by

M = 2 31 - 1

state = ( A * state ) % M; // Incorrect

Unfortunately, if this computation is done on 32-bit integers, the multipli-
cation is certain to overflow. Although Java provides a 64-bit long , using it
is more computationally expensive than working with int s, not all lan-
guages support 64-bit math, and even so, at that point, a larger value of
would be warranted. Later in this section, we use a 48-bit M , but for now
we use 32-bit arithmetic. If we stick with the 32-bit int , we could argue
that the result is part of the randomness. However, overflow is unacceptable
because we would no longer have the guarantee of a full period. A slight
reordering allows the computation to proceed without overflow. Specifi-
cally, if Q and R are the quotient and remainder of

Because of over-
flow, we must rear-
range calculations.

M

MA ⁄ , then we can

rewrite Equation 9.1 as

X i = AX i mod Q ( ( ) ) - RX i / Q + M δ X ()

(9.4)

+ 1

and the following conditions hold (see Exercise 9.5).

n The first term can always be evaluated without overflow.
n The second term can be evaluated without overflow if .
n δ( X i ) evaluates to 0 if the result of the subtraction of the first two terms is
positive; it evaluates to 1 if the result of the subtraction is negative.

RQ <

For the values of M and A , we have Q = 44,488 and R = 3,399. Consequently,
and a direct application now gives an implementation of the Random class
for generating random numbers. The resulting code is shown in Figure 9.2. The
class works as long as int is capable of holding M . The routine nextInt returns the
value of the state.
Several additional methods are provided in the skeleton given in
Figure 9.1. One generates a random real number in the open interval from 0 to 1,
and another generates a random integer in a specified closed interval (see the
online code).

Stick with these
numbers until you
are told otherwise.

RQ <