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 260 to 22000000. 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 260 to 22000000. As with all pseudorandom number generators, the resulting sequences are functions of the supplied seed values. An MWC generator is a special form of Lehmer random number generator xn = bxn−1 mod p which allows efficient implementation of a prime modulus 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, so multiplying by b is done implicitly by shifting one word. The MWC multiplier a and lag r determine the modulus p = abr−1. a is chosen so the modulus is prime and the multiplier has long period. The base b is typically chosen to equal the computer's word size, as this makes arithmetic modulo b trivial. This may vary from b = 28 for a microcontroller to b = 264. (This article uses b = 232 for examples.) Sometimes an odd base is preferred, in which case b = 2k − 1 can be used, which is almost as simple to implement. The period of a lag-r MWC generator is the order of b in the multiplicative group of numbers modulo p = abr − 1. While it is theoretically possible to choose a non-prime modulus, a prime modulus eliminates the possibility of the initial seed sharing a common divisor with the modulus, which would reduce the generator's period. Because 2 is a quadratic residue of numbers of the form 8k±1, b = 2k cannot be a primitive root of p = abr − 1. Therefore MWC generators with base 2k have their parameters chosen so their period is (abr−1)/2. This is one of the difficulties that use of b = 2k − 1 overcomes. The basic form of an MWC generator has parameters a, b and r, and r+1 words of state. The state consists of r residues modulo b