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. It involves simple computational integer-arithmetic, and leads to high-speed generation of sequences of random numbers with immense periods (ranging from around 2 60 {\displaystyle 2^{60}} to 2 2 , 000 , 000 {\displaystyle 2^{2,000,000}} ); those are its main advantages. As with all pseudorandom number generators, the resulting sequences are functions of the supplied seed values.
General theory An MWC generator is a special form of Lehmer random number generator x n = b x n − 1 mod p {\displaystyle x_{n}=bx_{n-1}{\bmod {p}}} which allows efficient implementation of a prime modulus p {\displaystyle p} much larger than the machine word size. Normal Lehmer generator implementations choose a modulus close to the machine word size. An MWC generator instead maintains its state in base b {\displaystyle b} , so multiplying by b {\displaystyle b} is done implicitly by shifting one word. The base b {\displaystyle b} is typically chosen to equal the computer's word size, as this makes arithmetic modulo b {\displaystyle b} trivial. This may vary from b = 2 8 {\displaystyle b=2^{8}} for a microcontroller to b = 2 64 {\displaystyle b=2^{64}} . (This article uses b = 2 32 {\displaystyle b=2^{32}} for examples.) The initial state ("seed") values are arbitrary, except that they must not be all zero, nor all at the maximum permitted values ( x 0 = b − 1 {\displaystyle x_{0}=b-1} and c 0 = a − 1 {\displaystyle c_{0}=a-1} ). (This is commonly done by choosing c 0 {\displaystyle c_{0}} between 1 and a − 2 {\displaystyle a-2} .). The MWC sequence is then a sequence of pairs x n , c n {\displaystyle x_{n},c_{n}} determined by
x n = ( a x n − 1 + c n − 1 ) mod b , c n = ⌊ a x n − 1 + c n − 1 b ⌋ {\displaystyle x_{n}=(ax_{n-1}+c_{n-1})\,{\bmod {\,}}b,\ c_{n}=\left\lfloor {\frac {ax_{n-1}+c_{n-1}}{b}}\right\rfloor }
This is called a lag-1 MWC sequence. Sometimes an odd base is preferred, in which case b = 2 k − 1 {\displaystyle b=2^{k}-1} can be used, which is almost as simple to implement. A lag- r {\displaystyle r} sequence is a generalization of the lag-1 sequence allowing longer periods. The lag- r {\displaystyle r} MWC sequence is then a sequence of pairs
x n , c n {\displaystyle x_{n},c_{n}} (for n > r {\displaystyle n>r} ) determined by
… excerpt ends here. Continue reading the full article.
