In computer science, 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 260 to 22000000.
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.
The lag-r MWC sequence is then a sequence of pairs xn, cn determined by
and the MWC RNG output is the sequence of x's,
The period of a lag-r MWC RNG is the order of b in the multiplicative group of numbers modulo abr − 1. It is customary to choose a's so that p = abr − 1 is a prime for which the order of b can be determined. Because b = 232 cannot be a primitive root of p = abr − 1, there are no MWC RNGs for base 232 that have the maximum possible period, one of the difficulties that use of b = 232 − 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.
Linear congruential generators are implemented as
A lag-1 multiply-with-carry RNG allows us to make the period nearly 264 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's 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,
The period of the resulting multiply-with-carry sequence will be the order of b = 232 in the multiplicative group of residues modulo ab − 1, that is, the smallest n such that b32n = 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 264, 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 , the congruential sequence
has this sequence of adjoining registers:
and the output sequence of x's, (the rightmost register), has period 4:
Starting with , the MWC sequence
has this sequence of adjoining registers
with output sequence of x's having period 22:
Notice that if those repeated segments of x values are put in reverse order,
This is true in general: The sequence of x's produced by a lag-r MWC RNG:
when put in reverse order, will be the base-b expansion of a rational j/(abr − 1) for some 0 < j < abr.
Also notice that if, starting with , we generate the ordinary congruential sequence
This is true in general, (but apparently only for lag-1 MWC sequences):
Given initial values , the sequence resulting from the lag-1 MWC sequence
is exactly the congruential sequence ynayn − 1 mod(ab − 1), reduced modulo b.
Choice of initial value y0 merely rotates the cycle of x's.
But a prime of the form p = abr + 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 = abr + 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 abr + 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
There is a slight change in the generation of a new pair (x, c):
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 abr+1, and the output x's, in reverse order, will form the base b expansion of j/(abr+1) for some 0<j<abr.
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=232, the period of the lag-1024 CMWC
With b = 232 and a = 3636507990, p = ab1359 − 1 is a safe prime, so the MWC sequence based on that a has period 3636507990243487 1030152.
With b = 232, a CMWC RNG with near record period may be based on the prime p = 15455296b42658 + 1. The order of b for that prime is 241489*21365056, about 10410928.
US Patent Issued to Samsung Electronics on June 26 for "Signal Processing Apparatus and Method for Performing Modular Multiplication in an Electronic Device, and Smart Card Using the Same" (South Korean Inventors)
Jul 03, 2012; ALEXANDRIA, Va., July 3 -- United States Patent no. 8,209,369, issued on June 26, was assigned to Samsung Electronics Co. Ltd....
Hanover Capital Sees Loss, May Consider Sale of Subsidiary.(Hanover Capital Mortgage Holdings Inc., REIT)(Brief article)
Jul 01, 2006; EDISON, NJ -- Hanover Capital Mortgage Holdings reported a net loss of $700,000, or $0.08 per share, in the first quarter of...