Thursday, November 3, 2011

The MOST EFFICIENT pseudo random number generator

I exumed Marsaglia's Complementary Multiply with Carry (CMWC) algorithm years ago in pursuit of implementing a really efficient random number generator on a 32-bit system that has a full 64-bit result from its 32x32 multiplier.  It so happens that in this case CMWC is really the most efficient algorithm that can  be thought up, and about a million times more efficient than Mersenne Twister, while Marsaglia has shown in multiple articles that its randomness appears to be as good as any existing psuedo-random number generator.

It was not easy to find all of the necessary information to implement it - I had to follow several threads from old newsgroups, and find copies of the referenced papers in particular in order to find a suitable value for "a", which is one of the factors in the repetitive multiplication.  I implemented it using four 32-bit seeds, which creates a very low likelihood of repetition (before the development of our Sun into a Red Giant).  I thought I was so clever to have unearthed such a great algorithm, so well suited to the hardware I was programming.

Well it turns out that Wikipedia now includes everything you need to know about CMWC.  They include an example C implementation with an apparently proper sample "a" value, and even use a default implementation of four 32-bit seeds.  This must be how it feels to finish your dissertation's bibliography just before Google Scholar comes out and electronic copies of journal articles are ubiquitous.  That Wikipedia page would have saved me A LOT of time...

Anyway, for everyone trying to generate random numbers quickly, check out CMWC - from my experience it is faster than anything else out there, and plenty random.

Edit: The Wikipedia implementation is for 4096 seeds of 32-bits, so not very compact relative to the four seed version - although changing to four seeds is not difficult, generating an "a" value that works for four seeds still requires a little bit of research.

No comments:

Post a Comment