Multiply-with-carry

From Wikipedia, the free encyclopedia

The introduction to this article provides insufficient context for those unfamiliar with the subject.
Please help improve the article with a good introductory style.

This article or section is in need of attention from an expert on the subject.

WikiProject Mathematics or the Mathematics Portal may be able to help recruit one.

If a more appropriate WikiProject or portal exists, please adjust this template accordingly.

Multiply-with-carry is a method invented by George Marsaglia for generating sequences of random integers based on an initial set of from two to many thousands of randomly chosen seed values. The main advantages of the Multiply-with-carry (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 most RNGs, the resulting sequences are functions of the randomly chosen seed values, but MWC RNGs seem to behave as well as—and often better—than others in tests of randomness.^{[citation needed]}

1 General theory
2 Comparisons with congruential RNGs
3 Complementary-multiply-with-carry RNGs
4 See also
- 4.1 References

[edit] General theory

A MWC sequence is based on arithmetic modulo a base b, usually b = 2³², because arithmetic modulo that b is automatic in most computers, but 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 that use of b = 2³² − 1 avoids.

In its most common form, a lag-r multiply-with-carry random number generator (MWC RNG) 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 c_r−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\ge r,$

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

x_'r' , x_r+1 , x_r+2, ...

The period of a lag-r MWC RNG 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 b = 2³² cannot be a primitive root of p = ab^r − 1, there are no MWC RNGs for base 2³² that have the maximum possible period, one of the difficulties that use of b = 2³² − 1 overcomes.

A theoretical problem with MWG 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.

[edit] Comparisons with congruential RNGs

Many congruential RNGs are implemented as

$x_n=ax_{n-1}+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 RNG allows us to make the period nearly 2⁶⁴ by using those same computer operations, except that this time we use the top half of the 64-bit product rather than ignore it after the 64 bits are formed. We use it 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.$

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⁶⁴, the maximum possible number of 32-bit pairs (x, c).

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

31,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:

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,...

Notice that if those repeated segments of x values are put in reverse order,

$449275\cdots97101275\,449725\cdots9710127\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 RNG:

$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_nay_n − 1 mod(ab − 1), reduced modulo b.

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

[edit] Complementary-multiply-with-carry RNGs

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 − l1 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⁴¹⁰⁹²⁸.

[edit] See also

Pseudorandom number generator

[edit] References

G. Marsaglia and A. Zaman, A new class of random number generators,

Annals of Applied Probability V. 1, No. 3, 462--480

G. Marsaglia, Random number generators,

Journal of Modern Applied Statistical Methods,V. 2, May 2003.

http://tbf.coe.wayne.edu/jmasm/vol2_no1.pdf

G. Marsaglia, On the randomness of Pi and other decimal expansions,

Interstat, October 2005, #5,

http://interstat.statjournals.net/YEAR/2005/articles/0510005.pdf

Couture, Raymond & L'Ecuyer, Pierre (1997), “Distribution properties of Multiply-with-carry random number generators”, Mathematics of Computation 66 (218): 591-607 .

Implementation in C++.

Categories: Pseudorandom number generators

Multiply-with-carry

From Wikipedia, the free encyclopedia

Contents

[edit] General theory

[edit] Comparisons with congruential RNGs

[edit] Complementary-multiply-with-carry RNGs

[edit] See also

[edit] References

Views

Navigation

Interaction

Search