Multiply-with-carry
The Multiply -with -carry (short: MWC ) and its modified version Complimentary - Multiply -with -carry (short: CMWC ) are pseudo-random number generators, which were presented in 2003 by George Marsaglia.
- 4.1 MWC
- 4.2 CMWC
Properties
Algorithm
The algorithm for the MWC is quite simple and can be described by two recurrence equations:
The result of the multiplication is divided into x ( the lower 32 bits ) and the carry C (upper 31 bits).
Here represents the i-th generated number, a is a constant factor and b is the number base.
The constants a and b should be chosen such that is a prime number. Then, from the generator for all non-trivial values and start a sequence of period length.
Example
Be, and as starting values :
Sequence length:
The MWC is in the reverse order of the decimal expansion of.
Complimentary Multiply -with -carry
In order to obtain a maximum period length is, for example, when using 32- bit integers for selected because this maximum exploits the range of values and is simultaneously to calculate very quickly. At MWC generators here but the period is shortened by half and it becomes more difficult to find suitable primes.
These problems can be solved by a small modification of the original algorithm, by using as recurrence equation
Be used.
Initialization
The initialization of the status register should be done with a sufficient number, preferably the (pseudo - ) randomly distributed bits. Otherwise, the generator a certain " warm-up " phase needs until he returns uniformly distributed random numbers.
Implementation
MWC
# include
# include