Random long, can it be twice in a row the same number

Question

I was wondering with the current java 1.7 implementation of the Random class, is it possible for the code below to generate two times the same random long?

Random rand = new Random((long) "some seed".hashCode());
while(rand.nextLong() != rand.nextLong()){

}

System.out.println("Will this text ever be on the console?");

Java source for nextLong() and next();

public long nextLong(){
    return ((long) next(32) << 32) + next(32);
}

protected synchronized int next(int bits){
    seed = (seed * 0x5DEECE66DL + 0xBL) & ((1L << 48) - 1);
    return (int) (seed >>> (48 - bits));
}

I would answer this question with false because I think the random method used by java does not repeat the same numbers for a 2^48 period, so it would never generate two the same numbers in a row. Is this correct?

Answer 1

To come up with an "longer" answer than my previous:

You already linked the implementation, it looks like:

public long nextLong(){
    return ((long) next(32) << 32) + next(32);
}

So, obviously, ONE random number calls 2 times next(32). That means, 2 random numbers will be equal, if next(32) results in 4 times THE SAME number because the rest of the function is "hardcoded".

Looking at the next() function, we can see the following:

protected synchronized int next(int bits){
    seed = (seed * 0x5DEECE66DL + 0xBL) & ((1L << 48) - 1);
    return (int) (seed >>> (48 - bits));
}

The return part can be simply ignored, because again: SAME seed would lead to the SAME return value - otherwhise your CPU is broken.

So, in total: We only need to focus on the line

seed = (seed * 0x5DEECE66DL + 0xBL) & ((1L << 48) - 1);

if that will result in the SAME seed, for four times, 2 random numbers have been generated, that are equal.

(Note: Sequences like a,b,a,b can be excluded to produce the same result. Post is long enough, i skip that part.)

---

First, lets eliminate the << 48 part. What does that mean? The Number given (1) will be shifted left 48 times. So the binary 0...01 will turn into 1000000000000000000000000000000000000000000000000 (48 zeros) then, one is subtracted, so what you will get is 0111111111111111111111111111111111111111111111111 (47 ones)

Lets have a look at the first part of that equation:

(seed * 0x5DEECE66D[L] + 0xB[L])

Note, that the ending [L] will only cause it to be a long value instead of a integer.

so, in binary words, that means:

seed * 10111011110111011001110011001101101 + 1011

After all, the function looks like

seed = (seed * 10111011110111011001110011001101101 + 1011) & (0111111111111111111111111111111111111111111111111)

(I left out the leading zeros on the first values)

So, what does & (0111111111111111111111111111111111111111111111111) do ?

The bitwise-and-operator and basically compares EVERY position of two binary numbers. And only if BOTH of them are "1", the position in the resulting binary number will be 1.

this said, EVERY bit of the equation (seed * 10111011110111011001110011001101101 + 1011) with a position GREATER than 48 from the RIGHT will be ignored.

The 49th bit equals 2^49 or 562949953421312 decimal - meaning that & (0111111111111111111111111111111111111111111111111) basically just says that the MAXIMUM result can be 562949953421312 - 1. So, instead of the result 562949953421312 - it would produce 0 again, 562949953421313 would produce 1 and so on.

All the stuff I wrote above could be easily verified:

While the following code will produce the random seed *11*:

private Long seed = 0L;

protected synchronized int next(int bits){
    seed = (seed * 0x5DEECE66DL + 0xBL) & ((1L << 48) - 1);
    System.out.println(seed);
    return (int) (seed >>> (48 - bits));
}

One can reverse engineer the seed and ALSO gets the seed 11 from a non-0 seed, using the number 562949953421312L.

private Long seed = 562949953421312L - 0xBL / 0x5DEECE66DL;

protected synchronized int next(int bits){
    seed = (seed * 0x5DEECE66DL + 0xBL) & ((1L << 48) - 1);
    System.out.println(seed);
    return (int) (seed >>> (48 - bits));
}

So, you see: Seed 562949953421312 equals Seed 0.

Easier proof:

Random r = new Random(0L);
Random r2 = new Random(562949953421312L);

if (r.nextLong()==r2.nextLong()){
    System.out.println("Equal"); //You WILL get this!
}

it continous of course:

Random r3 = new Random(1L);
Random r4 = new Random(562949953421313L);

if (r3.nextLong()==r4.nextLong()){
    System.out.println("Equal");
}

Why is this "magic number" (562949953421312L) important?

Assuming, we are starting with Seed 0.

The the first new-seed will be: 0 * 10111011110111011001110011001101101 + 1011 = 1011 (dec: 11)

The next seed would be: 1011 * 10111011110111011001110011001101101 + 1011 = 100000010010100001011011110011010111010 (dec: 277363943098)

The next seed (call 3) would be: 100000010010100001011011110011010111010 * 10111011110111011001110011001101101 + 1011 = 10000100101000000010101010100001010100010011100101100100111101 (dec 2389171320405252413)

So, the maximum number of 562949953421312L is exceeded, which will cause the random number to be SMALLER than the above calculated value.

Also, adding 1011 will cause the result to alternate between odd and even numbers. (Not sure about the real meaning - adding 1 could have worked as well, imho)

So, generating 2 seeds (NOT random numbers) ensures, that they are NOT equal, because a specific "overflow" point has been selected - and adding the MAXIMUM value (562949953421312L) is NOT enough to hit the same number within 2 generations.

And when 2 times the same seed is impossible, 4 times is also impossible, which means, that the nextLong() function could never return the same value for n and n+1 generations.

I have to say, that I wanted to proof the opposite. From a statistical point of view, 2 times the same number is possible - but maybe that's why it's called Pseudorandomness :)

Answer 2

No, getting two identical longs in a row with this algorithm is impossible.

While people were writing long posts about math and other wizardry, I went the code monkey route and brute forced the 2^48 possible seeds over the weekend. No two longs produced in a row were ever equal for any seed.

---

long int seed = 0;

int next(int bits){
    seed = (seed * 0x5DEECE66DL + 0xBL) & ((1L << 48) - 1);
    return (int) (seed >> (48 - bits));
}
long int nextLong(){
    return ((long int) next(32) << 32) + next(32);
}

int main(int argc, char** argv) {
  long int step = atoi(argv[1]);
  long int i = step << 32;
  long int end = (step+1) << 32;
  while(i < end) {
    seed = i;
    if(nextLong() == nextLong()) {
      printf("Found seed %ld\n", i);
      return 0;
    }
    ++i;
  }
  printf("No seed in %ld\n", step);
  return 1;
}

then

echo {0..65535} | xargs -n 1 -P 12 ./executable