Why does Random.nextLong not generate all possible long values in Java?

Question

The Javadoc of the nextLong() method of the Random class states that

Because class Random uses a seed with only 48 bits, this algorithm will not return all possible long values. (Random javadoc)

The implementation is:

return ((long)next(32) << 32) + next(32);

The way I see it is as follows: to create any possible long, we should generate any possible bit pattern of 64 bits with equal likelihood. Assuming the calls to next(int) give us 32 random bits, then the concatenation of these bits will be a sequence of 64 random bits and hence we generate each 64 bit pattern with equal likelihood. And therefore all possible long values.

I suppose that the person who wrote the javadoc knows better and that my reasoning is flaw somehow. Can anyone explain where my reasoning is incorrect and what kind of longs will be returned then?

Answer 1

Since Random is pseudo-random we know that given the same seed it will return the same values. Taking the docs at their word there are 48 bits of seed. This means there are at most 2^48 unique values that can be printed out. If there were more that would mean that some value that we used before in position < 2^48 gives us a different value this time than it did last time.

If we try to join up two results what do we see?

|a|b|c|d|e|f|...|(2^48)-1|

Above are some values. How many pairs are there? a-b, b-c, c-d,... (2^48)-1-a. There are also 2^48 pairs. We can't fill all values of 2^64 with only the 2^48 pairs.