
Java tutorials home
java.util.Random
Random number generators
XORShift
High quality random
Seeding generators
Entropy
SecureRandom
Random sampling
Random simulations and nextGaussian()
java.lang.Random falls "mainly in the planes"The Java Random class uses an algorithm called a Linear Congruential Generator, as discussed on the previous page. As mathematics researcher George Marsaglia famously described^{1}, one of the flaws of this algorithm is that the random numbers it generates "fall mainly in the planes". We'll look at what that means here. "Random" points plotted on a cube using the infamous RANDU algorithm. The problem manifests itself when we pull out series of numbers at a time from the generator. For reasons that will become clear, the problem is easiest to visualise with series of 3 numbers. Imagine we have a cube, which we will fill by plotting random points. We repeatedly take 3 numbers from our random nunmber generator, which we use for the x, y and z coordinates of the point. Doing this enough times, we'd eventually expect to fill the volume of the cube, given a couple of extra conditions^{2}. But when we use a LCG, however large the period, what we actually find is that all of the points generated lie on a limited number of equallyspaced "planes" intersecting the cube. If you're not used to thinking mathematically about "planes", imagine a number of blades cutting through a block of cheese. Writing a computer program to plot our points on a cube, we end up with something such as the one opposite. Now, the seriousness of this problem depends on the parameters of the LCG (the values of a, c and m in the LCG equation introduced on the previous page). For illustration, we picked a particularly bad combination: the RANDU generator, something of a legend in how not to implement a random numbe rgenerator, and unfortunately used in various mainframes and scientific experiments until at least some time in the 1970s^{3}. But even though this is pretty much the worst example there is, all LCG random number generators— including java.lang.Random— suffer from essentially the same problem, just on a smaller scale. With some slightly judicious mathematics, Marsaglia showed that the maximum number of planes depends on the modulus of the LCG (2^{48} in the case of java.lang.Random, 2^{31} in the case of RANDU), and on the number of dimensions. (The problem is easier to visualise in 2 or 3 dimensions, but mathematically, it extrapolates to any number of dimensions.) The bigger the modulus and the smaller the number of dimensions, the better:
maximum planes = (n! m) ^{1 / n}
where n is the number of dimensions, and m is the modulus. (The ! is the factorial operator, so 3! is 1x2x3=6, 4! is 1x2x3x4=24 etc.) For Java's java.lang.Random modulus of 2^{48}, this gives a maximum of just over 119,000 planes^{4}. This may not sound too bad, but it is something in the order of 0.003% of the theoretical maximum^{5}. Now you might be thinking, "well what the hell, I'm not using java.lang.Random to plot graphics". But see the illustration above as a graphical illustration of a mathematical problem: picking series of numbers from Random or any generator using the LCG algorithm will always introduce artefacts into the combinations of numbers produced. For example, generating strings of a certain length with successive calls to nextInt() will always produce strings with a subtle correlation between the characters in the string. Imagine then using these strings as test data for a hash table, and you might artificially get far more collisions than expected by chance, due to biases in the combinations of characters that the random number generator produced. So in general:
Avoid java.lang.Random (and any LCG) where you need to generate
very random combinations of values.
Of course, there are still cases where combinations produced by the Random class are "random enough". The class would generally be adequate for starting coordinates for objects in a simple game, for example. Next: randomness of different bit positionsOn the next page, we discuss another serious problem with LCG generators: namely that the randomness of generated bits varies according to their position. 1. Marsaglia, G., (1968), "Random Numbers Fall Mainly in the Planes",
Proceedings of the National Academy of Sciences, 61:2528.
2. We assume that the dimension of a 'point' is 1, and that the cube has dimensions of
n bits.
The generator's period would then have to be at least 2^{3n} for all
possible combinations of x, y and z to be created. If each
coordinate has the magnitude of an int (32 bits), this isn't actually possible
with java.lang.Random's period of 2^{48}. Written by Neil Coffey. Copyright © Javamex UK 2013. All rights reserved. 