I feel a bit cheated for not knowning, while I had several times seen the code the years before.
So it uses a good old linear congruential generator:
x = A * x + C
So, java.util.Random uses these two constants (A and C respectively):
private final static long multiplier = 0x5DEECE66DL;
private final static long addend = 0xBL;
Quite appropriate to place two "random" numbers in the Random class, right? Only these are not entirely random...
0x5DEECE66DL % 8 == 5
and
0xBL is an odd.
It turns out, when these exact conditions are satisfied, the defined period is maximal, so the generated period (x is long) is 2^64. This piece of magic is documented here, page 9. The "why" of it is beyond me.
If any ninja mathematician comes across this post, please leave some explanation if you can.
EDIT: oops. I overlooked that java.util.Random uses a mask to only reduce itself to 48 bits, instead of 64, so correspondingly the period is 2^48 instead of 2^64; apparently in an attempt to increase the quality of the generated numbers. In any case, if you need longer period, the technique described here will do the trick.
EDIT: oops. I overlooked that java.util.Random uses a mask to only reduce itself to 48 bits, instead of 64, so correspondingly the period is 2^48 instead of 2^64; apparently in an attempt to increase the quality of the generated numbers. In any case, if you need longer period, the technique described here will do the trick.
Many applications consume massive amounts of pseudorandom numbers; 2^64 is not "pretty darn long" at this scale.
ReplyDeleteFor example, the Mersenne Twister has a period of 2^19937 − 1.
http://en.wikipedia.org/wiki/Mersenne_twister
Umm... I think you need to put things into perspective. If an application consumes numbers at the incredible speed of 1 per nanosecond, it will take more than 6 centuries to cycle through all of them.
ReplyDeleteSecondly, Mersenne Twister has a *small* period compared to its state. The technique I mention gives the maximum possible period: given the same amount of memory, yields a period of 2^19968, i.e. a couple of billions larger!
N.B. If you take a look at the actual source code to java.lang.Random, you'll see the period is 2^48, not 2^64.
ReplyDeleteIncidentally, for many applications, this is poor!
Yep, you're right, appended a note above.
ReplyDelete