java.util.Random.nextInt(int n) has a very short period for values of n=2^k

Name: tb29552 Date: 11/05/98


Method java.util.Random.nextInt(n) has a very
short period for values of n equal to powers of 2.

For example, if n equals 2, 4, or 8, and if
a 166 mhz Pentium(tm)-class microcomputer is used,
then the values returned by calls to
java.util.Random.nextInt(n) may begin to repeat
in less than one minute.

This occurs because method
java.util.Random.nextInt(2) has a period of only
2^18, where 2^18=262144; that is,
java.util.Random.nextInt(2) begins to repeat
after only 262144 calls.

Similarly, java.util.Random.nextInt(4) has a
period of only 2^19=524288; and
java.util.Random.nextInt(8) has a period of only
2^20=1048576.

Because such periods can be exhausted in such a
short time, in my opinion this constitutes a bug.

In general, I think it will be found that
java.util.Random.nextInt(2^k) has a period of
only 2^(k+17), where k=1,2,3,...,30.

This bug apparently occurs because
java.util.Random is a linear conguential
pseudorandom number generator which uses a
modulus which is a power of 2. The least
significant bits of integers generated by such
a pseudorandom number generator have a shorter
period than the most significant bits.
Method java.util.Random.nextInt(n) makes use only
of bits of lesser significance if n is "small"
power of two.

For more information on this problem,
see Donald E. Knuth (1997 [3rd edition].
The Art of Computer Programming. Volume 2.
Seminumerical algorithms. Addison-Wesley),
especially page 13 of section 3.2.1.1.

(See also:)
Random number generators: good ones are hard to find
                                 S. K. Park
                                 K. W. Miller
                           Communications of the ACM
                      Vol. 31, No. 10 (Oct. 1988), Pages 1192-1201
http://www.acm.org/pubs/citations/journals/cacm/1988-31-10/p1192-park/

(Review ID: 42121)
======================================================================