PRNG 3: Complementary Multiply-with-Carry   Leave a comment


Purpose

Following previous 2 posts about algorithms of pseudo-random number generator, this post introduces another one, complementary multiply-with-carry (CMWC), proposed by George Marsaglia (2002). For its extremely long period and statistical properties, it is considered the best PRNG as of today, along with Mersenne Twister (MT16670) by Matsumoto Makoto (1998). However, it has been proved that CMWC is much easier and faster than MT. Also, it often shows better performance than MT16670, and always passes all 16 PRN tests, while MT16670 sometimes fails some of them.

 

Concept

Basically, CMWC is a simple modification of linear congruential generator (LCG). The difference is, CMWC carries current PRN (seed for next PRN) to somewhere else by using floor function and modulus operation. For this simple additional operation, it weakens serial correlation in the sequence.

 

Details

CMWC is written as below;

\begin{cases} X_n = (m-1)-( (aX_{n-r} + C_{n-1}) \% m) \\ C_n = \left \lfloor \frac{aX_{n-r} + C_{n-1}}{m} \right \rfloor \end{cases}

where % means modulus operation. Parameters are as below;

m : modulus. It is usually given as m=2^{32}-1

a : multiply. It should be chosen to hold p=ab^r-1 is a prime to achieve maximum length period p – 1.

r : lag. It should be power of 2 for better performance. And also, it should hold n \ge r

As you can see, CMWC requires X_1 , \, \cdots , \, X_r as seeds for sequence X and C_{r-1} as seed for complement C. So it requires r + 1 seed values. It can be easily computed by LCG or any other PRNG.

Note: It must hold C_{r-1} \le a

 

Theory

You can find it is very similar to LCG; actually, the algorithm consists of an LCG and complement. It is so because it tries to make use of bits in both upper and lower half.

Remember LCG uses modulus operation. In terms of bits operation, modulus operation is dumping bits in upper half; say, if the modulus is 2^{32}, modulus operation would yield values between 0 and 2^{32}-1, in other words, all bits above 31st digit will be dumped away.

On the other hand, the complement uses floor function. Therefore, whatever its result is, parts of any number less than 2^{32} is ignored. In terms of bits operation, it means dispose of lower-half bits.

Therefore, finally, we can say CMWC is an LCG (upper-half bits operator) with variable complementary of lower-half bits. More strictly, CMWC generates PRNs by subtraction of upper- and lower-half bits operation from maximum period.

As always in PRNGs, parameters should be chosen carefully; but this job has already been done by developer.

CMWC

Appropriate parameters for CMWC. (Source: “Random Number Generator”, Applied Journal of Statistics, 2003, George Marsaglia)

My appreciation to Prof. Marsaglia for his simple yet excellent algorithm and this table.

About these ads

Posted 2011/05/15 by Len in Pseudo-Random Number Generator

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

Follow

Get every new post delivered to your Inbox.

%d bloggers like this: