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

Question

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

This 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!

Answer 1

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

Answer 2

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.