Warp <war### [at] tagpovrayorg> wrote:
> Cousin Ricky wrote:
> > All that means is that POV uses better
> > LCG parameters than IBM did.
>
>   I'm pretty certain that's not the case, and that the difference you
> are seeing is caused by your choice of bits in the returned values,
> rather than the quality of the LCG.

Actually, the issue with the RANDU LCG was a quality issue, and had nothing to
do with regular patterns in the lower bits. That series of screenshots in the
randu.jpg shows the entire unit cube. There really are just 15 planes in that
cube:
http://en.wikipedia.org/wiki/RANDU

There may be a high degree of "randomness" in the upper 8 bits, but if you take
any three consecutive outputs from the randu generator, they will fall on one
of those 15 planes. The density of the lattice within any particular plane is
very high, but the spacing between the planes is orders of magnitude larger.

Imagine a random number generator that returned ordered triples in the unit
cube, such that x could be one of the 1000 values {0.000, 0.001, 0.002, ...,
0.999}, and y could be any of the same 1,000 values, but z could only be one of
the three values {0.1, 0.5, or 0.9}. You have a total of 3 million possible
combinations.

Would you consider that high quality? In effect, this was the flaw with randu.
This is IN ADDITION TO the "one big flaw" that you went on to describe!

>   LCGs have one big flaw: If you take the lowest bits, they tend to show
> regular patterns. For example, doing something like this (in pseudocode):
>
>     putpixel(rand() % 256, rand() % 256)
>
> is *very* likely to produce visible regular patterns. That's because the
> least-significant 8 bits of the values returned by the RNG are used
> as-is to generate the locations of the pixels.

As far as random number generators go, there are plenty of generators out there
that are simple, efficient, and far more effective than an LCG. One of the more
popular generators these days is the Mersenne Twister. It is, however, quite
complex and even a bit slow, compared to other generators that produce similar
quality random numbers (unless you need trillions of random numbers in a single
simulation).

A few variants I would recommend are the KISS generator (actually combines three
small but very fast generators), or a small period MWC or CMWC generator
("lag-4" with base 2^32 or (2^32)-1 is more than sufficient for most purposes,
though larger variants don't add complexity, so the sky's the limit). Google
"Marsaglia" for more info on MWC and CMWC generators.

Post a reply to this message