11

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?

miselico
  • 355
  • 3
  • 9
  • possible duplicate of [why 48 bit seed in util Random class?](http://stackoverflow.com/questions/2213882/why-48-bit-seed-in-util-random-class) – Engineer2021 Mar 25 '14 at 18:12
  • 3
    My guess is this can't generate numbers where first half equals second half. If they did `next(32)` would always generate the same number. Which would mean that you always generate the same long every time you called it. – FDinoff Mar 25 '14 at 18:18

3 Answers3

4

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.

Paul Rubel
  • 26,632
  • 7
  • 60
  • 80
0

Pseudo-Random Number Generators are like giant rings of numbers. You start somewhere, and then move around the ring step by step, as you pull numbers out. This means that with a given seed - an initial internal state - all subsequent numbers are predetermined. Therefor, since the internal state is only 48 bits wide, only 2 to the power 48 random numbers are possible. So since the next number is given by the previous number, it is now clear why that implementation of nextLong will not generate all possible long values.

Chris Vest
  • 8,642
  • 3
  • 35
  • 43
  • 2
    Strictly speaking, not the length of the seed value but the length of the internal state of the generator is relevant here. It seems to be the same for the used generator (I did not look this up though). – Henry Mar 25 '14 at 18:30
  • I don't buy that reasoning. If I do next(n) with n <= seed length, can I then get all possible n-bit values? You must prove that this is impossible, otherwise, if it is indeed possible, I can compose a number of any length from that smaller number of bits. – Ingo Mar 25 '14 at 18:33
  • Note that step in this case doesn't mean that values will go up until they wrap around (as you can tell by printing a few). It just means that the values are predetermined by the initial state. – Paul Rubel Mar 25 '14 at 18:34
  • The important part here (should be emphasized in bold of something) is `the next number is given by the previous number` – njzk2 Mar 25 '14 at 18:46
0

Let's say a perfect pseudo random K-bit generator is one that creates all possible 2^K seed values in 2^K trys. We can't do better, as there are only 2^K states, and every state is completly determined by the previous state and determines itself the next state.

Assume we write the output of the 48-bit generator down in binary. We get 2^48 * 48 bits that way. And now we can say exactly how many 64-bit sequences we can get by going through the list and noting the next 64 bits (wrapping to the start when needed). It is exactly the number of bits we have: 13510798882111488. Even if we assume that all those 64-bit sequences are pairwise different (which is not at all obvious), we have a long way to go until 2^64: 18446744073709551616.

I write the numbers again:

18446744073709551616 pairwise different 64 bit sequences we need
   13510798882111488 64 bit sequences we can get with a 48 bit seed.

This proves that the javadoc writer was right. Only 1/1844th of all long values can be produced with the random generator

Ingo
  • 36,037
  • 5
  • 53
  • 100
  • If the generator has an internal state of 48 bits it is clear, that there are at most 2^48 possible states. Thus, no matter how you draw out 64 bits there are at most 2^48 possible bit sequences instead of the full 2^64. – Henry Mar 25 '14 at 19:03
  • A pseudo random K-bit generator which creates all possible 2^K values in 2^K tries is a very poor generator. In fact so poor we can distinguish it. Think birthday paradox. – user515430 Mar 25 '14 at 19:29
  • You are right, @Henry, now it see it also. Will edit my answer accordingly. – Ingo Mar 25 '14 at 21:58