Java Random, little change in seed causes only little change in output

While making a map generator in Java I found a rather unnerving problem with their random number generator, to specify, when two RNGs have very similar seeds (differing in small integers) their first output value will become very similar!

Example code:

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());

Th开发者_如何学运维is pretty much broke my faith in the original Java RNG, since I use coordinates to seed a map generator. Could someone suggest either a redefinition for the Random.next(int bits) method, or some other fix for this problem?

Thank you for your help!

did you compare the sequence of the first ~20 values you get from 100000 and 100001?

these are the first 20 nextInts of seeds 100000 and 100001 resp. with in the third column the amount of different bits (bitcount of the xor between the 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 so similar after 3-5 iterations he

besides the standard Random implements a linear congruential RNG which is known not to be the best pseudo-random implementation in existence but the most efficient with memory (only one 64bit word for a period of 2^48)

for the interested the multiplier is 0x5deece66dL and c is 0xbL

Your two seeds (PRNG states) differ only by the least significant bit. Considering that PRNGs usually just do some xor-ing and shifting this shouldn't be too surprising.

You shouldn't use Random like this anyway. The state of the PRNG will be updated (state / seed will change by about 50 % of the 48 available bits) upon each nextInt method. That's all you should care about.

As I understand, you want a sequence of random numbers that depends on some computed seed, such that you can re-generate the sequence any time when given the same seed. Is that right?

The random number sequence generated by similar seeds starts similar, but soon diverges. You might get results that better fit your need, if you just skip over the first k values. Here, k is a number you have to determine, according to your need of dissimilarity of the sequence and speed of computation.

java.security.SecureRandom was introduced to deal with problems in java.util.Random such as the one described in the question. SecureRandom does not exhibit the same predictability (at least, it is not as blatantly obvious). You can fix the problem by using SecureRandom in your code instead of Random as the former is a subclass of the latter.

One might wonder why Sun didn't just fix Random after this problem was discovered. The reason is backward compatibility -- the behaviour of Random could not be changed because it would break existing code that depended upon the particular pseudo-random sequence generated by any given seed.