Java Random, a small change in seed causes only minor changes in output

Question

When creating a map generator in Java, I found a rather nasty problem with their random number generator, to indicate when two RNGs have very similar seeds (differing by small integers), their first output value will become very similar!

Code example:

Random r = new Random(); long n = 100000; //Choose any number r.setSeed(n); System.out.println(r.nextInt()); r.setSeed(n+1); System.out.println(r.nextInt()); 

This pretty much upset my belief in the original Java RNG, as I use the coordinates to sow the map generator. Can someone suggest either an override for the Random.next(int bits) method, or some other fix for this problem?

Thank you for your help!

Answer 1

Have you compared the sequence of the first ~ 20 values ​​that you get from 100000 and 100001?

these are the first 20 next rows of seeds 100000 and 100001, respectively. c in the third column the number of different bits (bit-bit xor between 2)

this last column should remain around 16

 -1986972922 -1987357671 13 -1760380366 -604895790 16 -1057894078 -329706441 15 -363772240 -1218064509 15 1545317691 -300240831 14 271304166 -900428132 21 1208561582 273461468 16 -1257783052 1069490639 16 -1549884799 40157720 15 -1514737808 -1818800021 17 -1030569735 1859508545 15 1310070992 880402584 18 -1513092400 971613287 19 -1993219517 354161779 16 -10847170 -204018237 15 -965377044 1488135032 14 802471291 1094582308 22 -539776032 -1021376555 15 2088199751 2070302462 12 -1271582124 64627614 19 

not very similar after 3-5 iterations he

in addition to the standard Random, it implements a linear congruent RNG, which, as you know, is not the best pseudo-random implementation, but is most efficient with memory (only one 64-bit word in a period of 2^48 )

for the interested factor 0x5deece66dL and c is 0xbL

Answer 2

Your two seeds (PRNG states) differ only in the least significant bit. Given that PRNGs usually just make some changes and offsets, this should not be too unexpected.

You should not use Random , as it is anyway. The PRNG state will be updated (state / seed will change by about 50% of the 48 available bits) for each nextInt method. That’s all you have to take care of.

Answer 3

As I understand it, you need a sequence of random numbers that depends on some calculated seeds, so you can regenerate the sequence at any time when the same seed is given. Is it correct?

The sequence of random numbers generated by such seeds starts similarly, but soon diverges. You can get results that better suit your needs if you just skip the first values ​​of k . Here k is the number you need to determine, according to your need for different sequence and speed calculations.

Answer 4

java.security.SecureRandom was introduced to solve problems in java.util.Random , such as those described in the question. SecureRandom does not have the same predictability (at least this is not so obvious). You can fix the problem by using SecureRandom in your code instead of Random , since the former is a subclass of the latter.

I wonder why Sun didn't just fix Random after this problem was discovered. The reason is backward compatibility - the behavior of Random cannot be changed, because it violates the existing code depending on the specific pseudo-random sequence generated by any given seed.