domingo, 27 de abril de 2008

Sun redefines randomness

It works very simply by repeatedly plotting the least significant bit of the java.util.Random.nextLong() method once for each point in the grid.

As you can probably see by the horizontal stripes, this 'random' method exibits significant periodic behavoiour.

Rather than looking like random static, the applet's display looks like a badly tuned-in television.

All Java virtual machines that are available to me appear to exhibit the same problem.

The nextInt method is also (approximately) half as seriously afflicted.

Observe that the applet displays a regular period - each fourth frame is the same.
As the grid is 128x128 this means the pattern repeats after a period of 65536, or 2^16 calls.
As the random number generator uses a long seed, this means that it fails to achieve its maximum period by a factor of 2^48!

Random number generation algorithms which exhibit such behaviour in their low bits are less than ideal for generating integers without post-processing.

The source code for the above applet is available for inspection here.

Sem comentários: