Why does java.util.Random use the mask?

Question

Simplified (i.e., leaving concurrency out) Random.next(int bits) looks like

protected int next(int bits) {
    seed = (seed * multiplier + addend) & mask;
    return (int) (seed >>> (48 - bits));
}

where masking gets used to reduce the seed to 48 bits. Why is it better than just

protected int next(int bits) {
    seed = seed * multiplier + addend;
    return (int) (seed >>> (64 - bits));
}

? I've read quite a lot about random numbers, but see no reason for this.

Answer 1

The reason is that the lower bits tend to have a lower period (at least with the algorithm Java uses)

From Wikipedia - Linear Congruential Generator:

As shown above, LCG's do not always use all of the bits in the values they produce. The Java implementation produces 48 bits with each iteration but only returns the 32 most significant bits from these values. This is because the higher-order bits have longer periods than the lower order bits (see below). LCG's that use this technique produce much better values than those that do not.

edit:

after further reading (conveniently, on Wikipedia), the values of a, c, and m must satisfy these conditions to have the full period:

1. c and m must be relatively primes

2. a-1 is divisible by all prime factors of m

3. a-1 is a multiple of 4 if m is a multiple of 4

The only one that I can clearly tell is still satisfied is #3. #1 and #2 need to be checked, and I have a feeling that one (or both) of these fail.

Answer 2

From the docs at the top of java.util.Random:

• The algorithm is described in The Art of Computer Programming,
• Volume 2 by Donald Knuth in Section 3.2.1. It is a 48-bit seed,
• linear congruential formula.

So the entire algorithm is designed to operate of 48-bit seeds, not 64 bit ones. I guess you can take it up with Mr. Knuth ;p