Alberto's Blog

Raydiant: Random generators

I find delightful the art of pseudorandom number generation. A bunch of generators has been tested before choosing one for the Raydiant engine. Some of them have been found to be not so random by the simple method of drawing random points in an accumulation buffer. These are the bad sheep (see the screen shoots just to be sure):

• Park-Miller “minimal standard” 31 bit pseudo-random number generator, implemented with David G. Carta’s optimization: with 32 bit math and without division.

• Lehmer random number generator. For more details see: “Random Number Generators: Good Ones Are Hard To Find” by Steve Park and Keith Miller, Communications of the ACM, October 1988.

• Concatenation of following two 16-bit multiply with carry generators: x(n) = a*x(n-1)+carry mod 2^16 and y(n) = b*y(n-1)+carry mod 2^16. Number and carry packed within the same 32 bit integer. Pass all of the tests in Marsaglia’s “Diehard” battery of statistical tests.

• Combination of a Multiply with carry generator and a simple multiplicative generator. Returns x(n) + z(n) where x(n) = x(n-1) + x(n-2) mod 2^32 and z(n) = 30903 * z(n-1) + carry mod 2^16. Pass all of the tests in Marsaglia’s “Diehard” battery of statistical tests.

On the other hand there were other generators that didn’t show their true predictive nature and insisted on appearing as true random numbers:

• ANSI C pseudorandom number generator.
• Mersenne Twister pseudorandom number generator.
• Robert Jenkins’ IBAA generator. Pass all of the tests in Marsaglia’s “Diehard” battery of statistical tests.
• Combination of lagged Fibonacci generator and a multiply with carry generator. Returning x(n)+y(n) mod 2^32 where x(n)=x(n-99)*x(n-33)mod2^32, x’s odd and y(n)=30903*y(n-1)+carrymod2^16. Pass all of the tests in Marsaglia’s “Diehard” battery of statistical tests.
• A Combination of 2 multiple recursive generators. Has parameters for 3 different combos. Source: Pierre
  * L’Ecuyer, “Good Parameter Sets for Combined Multiple Recursive Random Number Generators.” Operations Research, vol.47 no.1 (1999), pp.159–164. Pass all of the tests in Marsaglia’s “Diehard” battery of statistical tests.
• Combination of 3 Tausworthe generators — assumes 32-bit integers, Source: Pierre L’Ecuyer, “Maximally
  Equidistributed Combined Tausworthe Generators”. Mathematics of Computation, vol.65, no.213(1996), pp203–213. Pass all of the tests in Marsaglia’s “Diehard” battery of statistical tests. Strong theoretical backing so far.
• Combination of 4 tausworth generators — assumes 32-bit integers, Sources: Pierre L’Ecuyer, “Tables of
  Maximally-Equidistributed Combined LFSR Generators.” Mathematics of Computation, vol.68, no 225(1999),  pp.261–269. Pass all of the tests in Marsaglia’s “Diehard” battery of statistical tests. Strong theoretical backing so far.

Other merits considered to choose the perfect one were fastness of set seed operation, low memory usage, length of period and of course random number generation performance. And the winner is…

• Combination of a shift-register sequence on a 32-bit vector, a linear congruential generator, and a multiply with carry sequence. Returns y+x+z where y(n) = b xor (b<<5), b = a xor (a>>17), a = y(n-1) xor (y(n-1)<<13)), x(n) = 69069*x(n-1)+1mod2^32 and z(n) = 2*z(n-1)+z(n-2)+carry mod 2^32. The period is > 2^127. Extremely high quality, extremely fast, ultra fast set seed, 32 bit random numbers. Pass all of the tests in Marsaglia’s “Diehard” battery of statistical tests.

These are the bad sheep, to appreciate the defects is imperative you see them at full size and 1 pixel per texel zoom. A couple billion points have been accumulated on each one: