Multiply-with-carry

In computer science, multiply-with-carry (MWC) is a method invented by George Marsaglia for generating sequences of random integers based on an initial set from two to many thousands of randomly chosen seed values. The main advantages of the MWC method are that it invokes simple computer integer arithmetic and leads to very fast generation of sequences of random numbers with immense periods, ranging from around 2⁶⁰ to 2^2000000.

As with all pseudorandom number generators, the resulting sequences are functions of the supplied seed values.

General theory

A MWC sequence is based on arithmetic modulo a base b, usually b = 2³², because arithmetic modulo of that b is automatic in most computers. However, sometimes a base such as b = 2³² − 1 is used, because arithmetic for modulus 2³² − 1 requires only a simple adjustment from that for 2³², and theory for MWC sequences based on modulus 2³² has some nagging difficulties avoided by using b = 2³² − 1.

In its most common form, a lag-r MWC generator requires a base b, a multiplier a, and a set of r+1 random seed values, consisting of r residues of b,

x₀, x₁, x₂,..., x_r−1,

and an initial carry cr−1 < a.

The lag-r MWC sequence is then a sequence of pairs x_n, c_n determined by

x_{n}=(ax_{{n-r}}+c_{{n-1}})\,{\bmod \,}b,\ c_{n}=\left\lfloor {\frac {ax_{{n-r}}+c_{{n-1}}}{b}}\right\rfloor ,\ n\geq r,

and the MWC generator output is the sequence of x's,

x_r , x_r+1 , x_r+2, ...

The period of a lag-r MWC generator is the order of b in the multiplicative group of numbers modulo ab^r − 1. It is customary to choose a's so that p = ab^r − 1 is a prime for which the order of b can be determined. Because 2 is a quadratic residue of numbers of the form 8k±1, b = 2³² cannot be a primitive root of p = ab^r − 1. Therefore there are no MWC generators for base 2³² that have the maximum possible period, one of the difficulties that use of b = 2³² − 1 overcomes.

A theoretical problem with MWC generators, pointed out by Couture and l'Ecuyer (1997) is that the most significant bits are slightly biased; complementary-multiply-with-carry generators do not share this problem: "We shall see that, for the complementary MWC, each bit of the output value is fair, that is, the two binary digits will appear equally often in a full period, a property not shared by MWC generators." They do not appear to elaborate further as to the extent of the bias. Complementary-multiply-with-carry generators also require slightly more computation time per iteration, so there is a tradeoff to evaluate depending on implementation requirements.

Comparisons with linear congruential generators

Linear congruential generators are implemented as

x_{{n+1}}=(ax_{n}+c)\ {\bmod \,}2^{{32}},

because most arithmetic processors are able to put the multiplier a and the current x in 32-bit registers, form the 64-bit product in adjoining registers, and take the lower 32 bits as the product, that is, form

a\times x\ {\bmod \,}2^{{32}}

Adding the 32-bit c to that lower half then provides (ax+c) mod 2³². If a mod 8 is 3 or 5 and c is odd, the resulting base 2³² congruential sequence will have period 2³².

A lag-1 multiply-with-carry generator allows us to make the period nearly 2⁶³ by using those same computer operations, except that this time the top half of the 64-bit product is used rather than ignored after the 64 bits are formed. It is used as a new carry value c rather than the fixed carry value of the standard congruential sequence: Get ax+c in 64-bits, then form a new c as the top half of those 64 bits, and the new x as the bottom half.

With multiplier a specified, each pair of input values x, c is converted to a new pair,

x\leftarrow (ax+c)\,{\bmod \,}2^{{32}},\ \ c\leftarrow \left\lfloor {\frac {ax+c}{2^{{32}}}}\right\rfloor .

If x and c are not both zero, then the period of the resulting multiply-with-carry sequence will be the order of b = 2³² in the multiplicative group of residues modulo ab − 1, that is, the smallest n such that bⁿ = 1 mod (ab − 1). If we choose an a of 28 to 31 bits such that ab−1 is a "safe prime", that is both ab − 1 and ab/2 − 1 are prime, then the period will be ab/2 − 1, approaching 2⁶³, which in practice may be an acceptably large subset of the number of possible 32-bit pairs (x, c).

Following are some maximal values of a for computer applications which satisfy the above safe prime condition:

Bits in a	b	Maximum a Such That ab−1 is a Safe Prime	Period
15	2¹⁶	2¹⁵−50 = 32,718	1,072,103,423
16	2¹⁶	2¹⁶−352 = 65,184	2,135,949,311
31	2³²	2³¹−563 = 2,147,483,085	4,611,684,809,394,094,079
32	2³²	2³²−178 = 4,294,967,118	9,223,371,654,602,686,463
64	2⁶⁴	2⁶⁴−742 = 18,446,744,073,709,550,874	170,141,183,460,469,224,887,945,252,369,640,456,191
128	2¹²⁸	2¹²⁸−10,408	2¹²⁷(2¹²⁸−10,408)−1
256	2²⁵⁶	2²⁵⁶−9166	2²⁵⁵(2²⁵⁶−9166)−1
512	2⁵¹²	2⁵¹²−150,736	2⁵¹¹(2⁵¹²−150,736)-1

However, as being a safe prime does not affect the randomness of the sequence, one may instead simply choose a such that the order of b is ab/2 − 1. The following are again maximum values of a of various sizes.

Bits in a	b	Maximum a Such that b has order ab/2−1	Period
15	2¹⁶	2¹⁵−29 = 32,739	1,072,791,551
16	2¹⁶	2¹⁶−22 = 65,514	2,146,762,751
31	2³²	2³¹−68 = 2,147,483,580	4,611,685,872,398,499,839
32	2³²	2³²−76 = 4,294,967,220	9,223,371,873,646,018,559
63	2⁶⁴	2⁶³−140 = 9,223,372,036,854,775,668	85,070,591,730,234,614,574,571,566,698,273,439,743
64	2⁶⁴	2⁶⁴−116 = 18,446,744,073,709,551,500	170,141,183,460,469,230,661,776,147,440,730,111,999

Here is a comparison of congruential and MWC sequences for the simple case of arithmetic modulo 10; here the "registers" are a single digit, adjoining registers are two digits:

Starting with $x_{0}=1$ , the congruential sequence

x_{n}=(7x_{{n-1}}+3)\,{\bmod \,}10,

has this sequence of adjoining registers:

10,03,24,31,10,03,24,31,10,\ldots ,

and the output sequence of x's, (the rightmost register), has period 4:

0,3,4,1,0,3,4,1,0,3,4,1,\ldots

Starting with $x_{0}=1,c_{0}=3$ , the MWC sequence

x_{n}=(7x_{{n-1}}+c_{{n-1}})\,{\bmod \,}10,\ c_{n}=\left\lfloor {\frac {7x_{{n-1}}+c_{{n-1}}}{10}}\right\rfloor ,

has this sequence of adjoining registers

10,01,07,49,67,55,40,04,28,58,61,13,22,16,43,25,37,52,19,64,34,31 10,01,07,...

with output sequence of x's having period 22:

0,1,7,9,7,5,0,4,8,8,1,3,2,6,3,5,7,2,9,4,4,1 0,1,7,9,7,5,0,...

Notice that if those repeated segments of x values are put in reverse order starting from a $x_{{22n+20}}$ ,

449275\cdots 97101\,449275\cdots 9710144\cdots

we get the expansion j/(ab−1) with a=7, b=10, j=31:

{\frac {31}{69}}=.4492753623188405797101\,4492753623\ldots

This is true in general: The sequence of x's produced by a lag-r MWC generator:

x_{n}=(ax_{{n-r}}+c_{{n-1}}){\bmod \,}b\,,\ \ c_{n}=\left\lfloor {\frac {ax_{{n-r}}+c_{{n-1}}}{b}}\right\rfloor ,

when put in reverse order, will be the base-b expansion of a rational j/(ab^r − 1) for some 0 < j < ab^r.

Also notice that if, starting with $x_{0}=34$ , we generate the ordinary congruential sequence

x_{n}=7x_{{n-1}}\,{\bmod \,}69

we get the period 22 sequence

31,10,1,7,49,67,55,40,4,28,58,61,13,22,16,43,25,37,52,19,64,34, 31,10,1,7,...

and that sequence, reduced mod 10, is

1,0,1,7,9,7,5,0,4,8,8,1,3,2,6,3,5,7,2,9,4,4, 1,0,1,7,9,7,5,0,...

the same sequence of x's resulting from the MWC sequence.

This is true in general, (but apparently only for lag-1 MWC sequences):

Given initial values $x_{0},c_{0}$ , the sequence $x_{1},x_{2},\ldots$ resulting from the lag-1 MWC sequence

x_{n}=(ax_{{n-1}}+c_{{n-1}})\,{\bmod b}\,,\ \ c_{n}=\left\lfloor {\frac {ax_{{n-1}}+c_{{n-1}}}{b}}\right\rfloor

is exactly the congruential sequence y_n = ay_n − 1 mod(ab − 1), reduced modulo b.

Choice of initial value y₀ merely rotates the cycle of x's.

Complementary-multiply-with-carry generators

Establishing the period of a lag-r MWC generator usually entails choosing multiplier a so that p=ab^r − 1 is prime. If p is a safe prime, then the order of b will be p − 1 or (p − 1)/2. Otherwise, it is likely that p − 1 will have to be factored in order to find the order of b mod p, and p = ab^r − 1 may be difficult to factor.

But a prime of the form p = ab^r + 1 will make p−1 easy to factor, so a version of multiply-with-carry that involves the order of b for a prime p = ab^r + 1 would reduce considerably the computational number theory required to establish the period of a MWC sequence.

Fortunately, a slight modification of the MWC procedure leads to primes of the form ab^r + 1. The new procedure is called complementary-multiply-with-carry (CMWC),

and the setup is the same as that for lag-r MWC: multiplier a, base b, r + 1 seeds

x₀, x₁, x₂, ..., x_r−1, and c_r − 1.

There is a slight change in the generation of a new pair (x, c): $x_{n}=(b-1)-(ax_{{n-r}}+c_{{n-1}})\,{\bmod \,}b,\ c_{n}=\left\lfloor {\frac {ax_{{n-r}}+c_{{n-1}}}{b}}\right\rfloor .$

That is, take the complement, (b−1)−x, when forming the new x.

The resulting sequence of x's produced by the CMWC RNG will have period the order of b in the multiplicative group of residues modulo ab^r+1, and the output x's, in reverse order, will form the base b expansion of j/(ab^r+1) for some 0<j<ab^r.

Use of lag-r CMWC makes it much easier to find periods for r's as large as 512, 1024, 2048, etc. (Making r a power of 2 makes it slightly easier (and faster) to access elements in the array containing the r most recent x's.)

Some examples: With b=2³², the period of the lag-1024 CMWC

x_{n}=(b-1)-(ax_{{n-1024}}+c_{{n-1}})\,{\bmod \,}b,\ c_{n}=\left\lfloor {\frac {ax_{{n-1024}}+c_{{n-1}}}{b}}\right\rfloor .

will be a $\cdot$ 2³²⁷⁶², about 10⁹⁸⁶⁷ for these three as: 109111 or 108798 or 108517.

With b = 2³² and a = 3636507990, p = ab¹³⁵⁹ − 1 is a safe prime, so the MWC sequence based on that a has period 3636507990 $\cdot$ 2⁴³⁴⁸⁷ $\approx$ 10¹³¹⁰¹.

With b = 2³², a CMWC RNG with near record period may be based on the prime p = 15455296b⁴²⁶⁵⁸ + 1. The order of b for that prime is 241489*2^1365056, about 10⁴¹⁰⁹²⁸.

Implementation

The following is an implementation of the CMWC algorithm in the C programming language. Also, included in the program is a sample initialization function. In this implementation the lag r=4096. The period of the resulting generator is about $2^{{131104}}$ .

// C99 Complementary Multiply With Carry generator
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <time.h>

// CMWC working parts
#define CMWC_CYCLE 4096 // as Marsaglia recommends
#define CMWC_C_MAX 809430660 // as Marsaglia recommends
static uint32_t Q[CMWC_CYCLE];
static uint32_t c = 362436; // must be limited with CMWC_C_MAX (we will reinit it with seed)

// Make 32 bit random number (some systems use 16 bit RAND_MAX [Visual C 2012 uses 15 bits!])
uint32_t rand32(void)
{
    uint32_t result = 0;
    result = rand();
    result <<= 16;
    result |= rand();
    return result;
}

// Init all engine parts with seed
void initCMWC(unsigned int seed)
{
    srand(seed);
    for (int i = 0; i < CMWC_CYCLE; i++) Q[i] = rand32();
    do c = rand32(); while (c >= CMWC_C_MAX);
}

// CMWC engine
uint32_t randCMWC(void)
{
    static uint32_t i = CMWC_CYCLE - 1;
    uint64_t t = 0;
    uint64_t a = 18782; // as Marsaglia recommends
    uint32_t r = 0xfffffffe; // as Marsaglia recommends
    uint32_t x = 0;

    i = (i + 1) & (CMWC_CYCLE - 1);
    t = a * Q[i] + c;
    c = t >> 32;
    x = t + c;
    if (x < c)
    {
        x++;
        c++;
    }

    return Q[i] = r - x;
}

int main()
{
    unsigned int seed = time(NULL);
    initCMWC(seed);
    printf("Random CMWC: %u\n", randCMWC());
}

Usage

Because of simplicity, speed, quality (it passes statistical tests very well) and astonishing period, CMWC is known to be used in game development, particularly in modern roguelike games. It is informally known as the Mother of All PRNGs. In libtcod, CMWC4096 replaced MT19937 as the default PRNG.^[1]

References

↑ "Random number generator - RogueBasin". www.roguebasin.com. Retrieved 2016-11-30.

Marsaglia, G.; Zaman, A. (1991). "A new class of random number generators". Annals of Applied Probability. 1 (3): 462–480. doi:10.1214/aoap/1177005878.
Marsaglia, G. (2003). "Random number generators". Journal of Modern Applied Statistical Methods. 2.
Marsaglia, George (2003). "Xorshift RNGs". Journal of Statistical Software. 8 (14): 1–6.
Marsaglia, G. (2005). "On the randomness of Pi and other decimal expansions" (PDF). Interstat. 5.
Couture, Raymond; L'Ecuyer, Pierre (1997). "Distribution properties of Multiply-with-carry random number generators". Mathematics of Computation. 66 (218): 591–607. doi:10.1090/S0025-5718-97-00827-2.
Press, WH; Teukolsky, SA; Vetterling, WT; Flannery, BP (2007). "Section 7.1.2.B Multiply With Carry (MWC)". Numerical Recipes: The Art of Scientific Computing (3rd ed.). New York: Cambridge University Press. ISBN 978-0-521-88068-8.

This article is issued from Wikipedia - version of the 12/1/2016. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.