Notes on delt0r’s post (some suggestions below):
LFSR = Linear Feedback Shift Register (MT is LFSR + tempering step)
delt0r’s generator is based on “Xorshift RNGs” by George Marsaglia. (As a side note: some of Doug Lea’s code was using this generator, so It might be being hidden in the current JDK in the concurrency stuff)
In real life when I need a good generator I use a variant of this presented by Richard Brent in “Some long-period random number generators”.
More RNG comments:
When performance is an issue I’m attempting to promote using the worst fastest (edit) generator possible that’s suitable for the task, and this is reasonable because all pseudo-random number generators are flawed. You simply choose one that has “faults” that either you don’t care about or are not pronounced enough to cause obvious defects. In my limited experience most RNG problems are usage based rather than having a bad generator.
Why would you want a long period? From the random texture example above it’s obvious that a period shorter than the “calculation” (the table random) is bad. The general rule-of-thumb for good properties is something like: “a single calculation should not need more than sqrt§ values”, where P is the period. (cube root if birthday-spacing) So if you have an RNG with period 2^31: you should be good for ~46K samples, for period 2^63 about 3 billion. But in most cases you don’t even care about that. Creating a 128x128x3 random texture is more than 46K, but using if you use two generators from the same family with 2^31 & 2^63 (or higher) periods, you won’t be able tell which is the better of the two.
Another big issue with PRNG’s is Marsaglia’s “fall mainly in the planes”, where they have lattice structures in higher dimensions. The wikipedia page has an animation of an LCG generating random points in 3D here which demo’s the problem. But, look again at texture’s by Markus_Persson above, which is another 3D sampling. Visually few people will see the “defects” of the two LCGs vs MT. And most games are constantly in motion, so the player doesn’t have time to ponder minor defects anyway.
Use a fast generator. If you don’t see defects, the quality is fine. If you do, make sure your not doing something funky.
As mentioned above I use a variant of above posted generator (in the rare instances I need something better than LCG). It can have good properties and be very fast. To make it fast, I use a longer period generator (which requires a seed array) and precalculate a “round” of values (MT does the same thing for it’s LFSR part). The main issue here is that each step has a dependecy chain the slows calculation if performed one at a time. Since it is a good quality generator, I also “cache” a single value and keep track of how many bits are left in the cache. When I need an n-bit number, the method grabs from this cached value.
This last sentence makes an obvious, but important point. Call (whatever) random less. If your PRNG creates ‘n’ good bits, use them as a collection if you easily can.
@delt0r: You might want to think about adding a decorrelation step to the seeding process.