Raydiant: Random generators

November 7, 2009 at 10:09 am | Posted in Computer path | 3 Comments
Tags: , , , , , , ,

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:

3 Comments »

RSS feed for comments on this post. TrackBack URI

  1. Hi great read. Is there a paper about the chosen solution? Because i am a bit confused about the constants I,R and L.

    Thanks

    • Thanks for pointing out that confusing part of the blog entry. I’ve modified it now and hope it will be clearer. Also if you find it useful I can post here the working C++ implementation.

  2. Hi Alberto,

    Yes, a C++ version of your RNG will be great… just to check that mine is correct 😛

    Thanks for the article


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Blog at WordPress.com.
Entries and comments feeds.

%d bloggers like this: