CODEWITHSUNDEEP
javarandom
Travis Well
Travis Well

Reputation: 965

Do Java Random instances with different seeds really produce different sequences, or do they start at different places in the same sequence?

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 possible that the two instances are now "synced up," so to speak, such that they will produce the same sequence of integers going forward indefinitely?

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 some seeds share sequences? (Or does it depend on which sea shore Sally sells sea shells on?)

Upvotes: 0

Views: 90

Answers (1)

Oliver Charlesworth
Oliver Charlesworth

Reputation: 272527

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 eventually reaches the starting state of rA. At that point, its output sequence will match that of rA.

Upvotes: 2

Related Questions