VERY ROUGH WORK IN PROGRESS..NO REAL USEFUL INFORMATION AS OF YET.

Overview

The purpose of this page is to give an rough overview of how pseudo random number generators (PRNG) work and a rough idea of how to choose ones which are adequte for a game runtime.

Introduction

The vast majority of PRNGs all work in the same way.  They take some state-data in the form of a sequence of bits and perform computations which mix the bits.  Notice that hashing and random number generation are very similar. A given generator will have a period which is the number of unique values the state will assume before wrapping around and repeating itself.  Yeah, that was clear.  OK, let's pretend like we're using a 2-bit integer for our state data, so our 2-bit integer can have values of: {0,1,2,3}.  For our random number generator we want to produce some permutation (MathWorld, Wikipedia) of that set which appears random.  The number of permutations of a set with n elements is Factorial[n], so we have 24 choices for our 2-bit integer.  Limiting the set to those that start with '0' (all the remaining are rotations), we have: {0,1,2,3},{0,1,3,2},{0,2,1,3},{0,2,3,1},{0,3,1,2},{0,3,2,1}.

Now obviously none of the above permutation choices look very random but this is exactly how random number generators work. The problem here is that there just aren't enough unqiue values that any of the permutations appear random.  Luckily factorials explode and if we were talking about only 8-bits then there'd be approximately 8.6x10⁵⁰⁶ choices and 16-bits is ~5.2x10²⁸⁷¹⁹³.  Other than some very narrow special cases (like in GLSL, when attempt to avoid using integers) there's no reason to use generators with less than 32-bits.

This does not imply that PRNGs with longer periods are superior in quality than those that are shorter.

Period

As mentioned above the period of a PRNG is the length of the sequence that it generates.  Once the period is exhausted, the sequence wraps-around and starts to repeat itself.

For scientific usage long periods are important.  The reason for this is that statistically they will begin show defects if in "single computation" more than sqrt(T) random numbers are used, where T is the period or the cube-root if the problem requires birthday spacing (Wikipedia).  Additionally long periods are considered desirable because one can break a problem across multiple CPUs/servers/whatever to attack a single problem and the longer the period, the lower the probablity that the individual computation units will be using overlapping parts of the sequence.  (An alternate solution is to use different generators per computation unit, but that's neither here-nor-there for our purposes) 

Note the "single computation" part.  There's the mistaken notion in games that one needs a period long enough that it never repeats during gameplay.  Not at all, it simply should be long enough that every single computation has more than enough values to complete.  To give a rough idea of 'scale', here's a table of common short periods with its square and cube roots:

T	Period (T)	T1/2	T1/3
232	4294967296	65536	1625.5
248	281474976710656	16777216	65536
264	18446744073709551616	4294967296	2642246
2128	340282366920938463463374607431768211456	18446744073709551616	6981463658332

Write something about using above as a rough guideline.

Dimensions

Humm...any ideas here kids, other than don't worry about dimensions.  Just don't use a LCG for more than 2.

Old Skool

Mention some mod-power-of-two LCGs here.  Non-power-of-two just ain't worthwhile.  Nor are IHMO sub-cycle generators.

New kids on the block

Mention some cheap LSFRs here

Quality

Write something somehow convicing about how quality a la. diehard and various crushes shouldn't matter.

Rules of thumb

Stuff like never use the same instance of a generator in more than one thread.  Likewise don't use or write static utilities methods.  Use different generators if you need a more expensive one for a sub-set of tasks...oh, and don't really worry about any of this stuff if you just don't generate many random numbers.

Reference
Blah, blah

This is exactly "counter" to what I'm attempting to say.  Which is, you don't (or rather shouldn't) directly care about how long it takes before the RNG starts to repeating itself.  If you're running through the period multiple times in a single frame...that doesn't directly matter.  Indirectly it might mean you're using an RNG with too short of a period...by which I mean "is too expensive per result", as you shouldn't be using anything with T shorter than 2^32 (again CPU only) of which there are fast good options.  OR it means you're generating tons of random numbers (sticking to 2^32) and generating more than 4x10^9 random numbers per game frame seems a bit excessive.  On the other hand, if a generator isn't going to repeat itself for a very long real-time, then that might again indicate that you're throwing too much processor time on random number generation (assuming T > 2^32 or perhaps 2^64).  Now this is completely counter-intuitive and many people will have trouble accepting this.

The purpose of the table with square and cube roots is (when I come up with some reasonable verbage) to give an idea of scale.  For gaming purposes is insanely unlikely that the cube-root number is useful.  I'm only including it for completeness AND as bound as people will tend to be somewhat paranoid about quality.  Likewise, the square root number is mostly overkill but should be sufficient target for an acceptable programmer comfort zone.  As mentioned above the sqrt & cube-root are rules of thumb from that statistics world about when a generator will start to show statistical defects IN A SINGLE PROBLEM.  So, say one thing you need to do is generator a bunch of random vectors in 3D at some uniform grid positions and do something with those values.  That's an example of a single problem.  Sticking to T=2^32, then sqrt(2^32) = 65536, divide by 3 (number of components/vector) = ~21845, cube root (for 3D) ~= 7281:  So if the uniform grid of vectors is smaller than or equal to 7281x7281x7281...then you should be more than comfortable with the period.  When the RNG moves on to the next problem, then you start anew.  So all you really care about is the scale of the single largest problem.

Nice feedback..thanks.  I work on adding the stuff you've mentioned.