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.

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,

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

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

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.

...
Wikipedia