Multiply-with-carry

The Multiply-with-Carry (short: MWC ) and its modified variant Complimentary-Multiply-with-Carry (short: CMWC ) are pseudo-random number generators , which were presented in 2003 by George Marsaglia .

properties

Extremely long period (2 ¹³¹⁰⁸⁶ for the CMWC with 16 kB status register).
Delivers an evenly distributed bit sequence.

algorithm

The algorithm for the MWC is quite simple and can be described by two recurrence equations:

{\ displaystyle x_ {n} = (ax_ {n-1} + c_ {n-1}) \ mod b}

{\ displaystyle c_ {n} = \ lfloor (ax_ {n-1} + c_ {n-1}) / b \ rfloor}

The result of the multiplication is divided into x(the lower 32 bits) and the carry c(the upper 31 bits).

Here stands for the i th generated number, a for a constant factor and b for the number base. ${\ displaystyle x_ {i}}$

The constants a and b should be chosen so that is a prime number. Then the generator outputs for all non-trivial start values and a sequence with the period length . ${\ displaystyle m = ab-1}$ ${\ displaystyle x_ {1}}$ ${\ displaystyle c_ {1}}$ ${\ displaystyle l = m-1}$

example

Be , and as initial values , : ${\ displaystyle a = 6}$ ${\ displaystyle b = 10}$ ${\ displaystyle c_ {1} = 3}$ ${\ displaystyle x_ {1} = 5}$

Sequence length: ${\ displaystyle l = m-1 = ab-2 = 6 \ cdot 10-2 = 58}$

{\ displaystyle x_ {n} = (6x_ {n-1} + c_ {n-1}) \ mod 10}

{\ displaystyle c_ {n} = \ lfloor (6x_ {n-1} + c_ {n-1}) / 10 \ rfloor}

n	${\ displaystyle (6x_ {n-1} + c_ {n-1})}$	${\ displaystyle c_ {n}}$	${\ displaystyle x_ {n}}$
1	-	3	5
2	33	3	3
3	21st	2	1
4th	8th	0	8th
5	48	4th	8th
6th	52	5	2

The MWC outputs the decimal fraction expansion of in reverse order . ${\ displaystyle 33 \ over 59}$

Complimentary multiply-with-carry

In order to obtain a maximum period length, z. B. when using 32-bit integers for selected, as this makes maximum use of the range of values and at the same time can be calculated very quickly. With MWC generators, however, the period is reduced by half and it becomes more difficult to find suitable prime numbers. ${\ displaystyle b = 2 ^ {32}}$

These problems can be remedied by a small modification of the original algorithm, using as a recurrence equation

{\ displaystyle x_ {n} = (b-1) - [(ax_ {n-1} + c_ {n-1}) \ mod b]}

used.

initialization

The status register should be initialized with bits that are as random as possible and evenly distributed, i.e. about as many 1 as 0 bits. Otherwise the generator needs a "warm-up phase", i. H. A certain amount of random numbers has to be generated until the generator delivers uniformly distributed random numbers.

implementation

MWC

#include <stdint.h>

static uint32_t Q[1038];
static uint32_t c = 123;

uint32_t MWC1038() {
    static uint32_t i = 1037;
    uint64_t t;

    t = (611376378ULL * Q[i]) + c;
    c = t >> 32;

    if (--i != 0)
        return (Q[i] = t);

    i = 1037;
    return (Q[0] = t);
}

CMWC

#include <stdint.h>

static uint32_t Q[4096];
static uint32_t c = 123;   /* 0 <= c < 18782 */

uint32_t CMWC() {
  static uint32_t i = 4095;
  uint64_t t;
  uint32_t x;

  i = (i + 1) & 4095;
  t = (18782ULL * Q[i]) + c;
  c = t >> 32;
  x = t + c;

  if (x < c) { ++x; ++c; }

  Q[i] = 0xfffffffe - x;

  return Q[i];
}

literature

G. Marsaglia: Random number generators . (PDF) In: Journal of Modern Applied Statistical Methods , V. 2, May 2003.
G. Marsaglia: On the randomness of Pi and other decimal expansions . (PDF) Interstat, October 2005, # 5

Web links

Statistical test library: TestU01
F. Panneton, P. L'Ecuyer: Improved Long-Period Generators Base on Linear Recurrences Modulo 2 . (PDF; 301 kB).
groups.google.com
groups.google.com