Travis Wellman - 9 months ago 28

Java Question

Imagine instantiating two Randoms with different seeds, rA and rB. See what the first integer generated by rA is. Then call nextInt() on rB until you get the same integer.

`groovy:000> rA = new Random()`

===> java.util.Random@463b4ac8

groovy:000> rB = new Random(1)

===> java.util.Random@5644dc81

groovy:000> rA_0 = rA.nextInt()

===> -1458003306

groovy:000> rB_0 = rB.nextInt()

===> -1155869325

groovy:000> for (int rB_n = rB.nextInt(); rB_n != rA_0; rB_n = rB.nextInt());

===> null

Is it

`groovy:000> rA.nextInt()`

===> 1701960179

groovy:000> rB.nextInt()

===> 1760857409

groovy:000> for (int rB_n = rB.nextInt(); rB_n != rA_0; rB_n = rB.nextInt());

===> null

groovy:000> rB.nextInt()

===> 614305687

The limited experiment shown does not discover such a collision of sequences, but it's hard to know if such a collision could be found.

To rephrase the question, are we working with one very long sequence, and the seed determines where on that sequence we start, or can Random instances with different seeds be depended on to actually produce entirely different sequences of numbers? Or worse, do

Answer

Java `Random.next()`

(which underlies all public `nextX()`

methods) is contractually obliged to follow the following LCG equation:

```
(x * 0x5DEECE66DL + 0xBL) & ((1L << 48) - 1)
```

Thus given a current state (`x`

), the next state is entirely determined.

So assuming that this is a "full-cycle" LCG (i.e. it iterates over all possible values), then it must be the case that `rB`

must eventually reach the starting state of `rA`

. At that point, its output sequence will match that of `rA`

.