Multiply-with-carry

Der Multiply-with-Carry (kurz: MWC) und dessen modifizierte Variante Complimentary-Multiply-with-Carry (kurz: CMWC) sind Pseudozufallszahlengeneratoren, die 2003 von George Marsaglia vorgestellt wurden.

Eigenschaften

1. Extrem lange Periode (2¹³¹⁰⁸⁶ für den CMWC mit 16 kB Zustandsregister).
2. Liefert gleich verteilte Bit-Sequenz.

Algorithmus

Der Algorithmus für den MWC kann durch zwei Rekurrenzgleichungen beschrieben werden:

$x_n=(a{x}_{n-1}+c_{n-1})modb$

$c_n=\lfloor (a{x}_{n-1}+c_{n-1})/b\rfloor$

Das Ergebnis der Multiplikation ist aufgeteilt in x (die unteren 32 Bits) und den Übertrag c (die oberen 31 Bits).

Hier steht $x_i$ für die i-te generierte Zahl, a für einen konstanten Faktor und b für die Zahlenbasis.

Die Konstanten a und b sollten so gewählt werden, dass $m=ab-1$ eine Primzahl ist. Dann gibt der Generator für alle nicht-trivialen Startwerte $x_1$ und $c_1$ eine Sequenz mit der Periodenlänge $l=m-1$ aus.

Beispiel

Sei $a=6$, $b=10$ und als Startwerte $c_1=3$, $x_1=5$:

Sequenzlänge: $l=m-1=ab-2=6\cdot 10-2=58$

$x_n=(6x_{n-1}+c_{n-1})mod10$

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

n	$(6x_{n-1}+c_{n-1})$	$c_n$	$x_n$
1	–	3	5
2	33	3	3
3	21	2	1
4	8	0	8
5	48	4	8
6	52	5	2

Der MWC gibt in umgekehrter Reihenfolge die Dezimalbruchentwicklung von $\frac{33}{59}$ aus.

Complimentary Multiply-with-carry

Für die Erzielung einer maximalen Periodenlänge wird beispielsweise bei Verwendung von 32-Bit-Integern für $b=2^{32}$ gewählt. Dies ermöglicht die optimale Nutzung des Wertebereichs und eine gleichzeitig schnelle Berechnung. Bei MWC-Generatoren verkürzt sich hier aber die Periode um die Hälfte und es wird schwieriger, passende Primzahlen zu finden.

Diese Probleme können durch eine kleine Modifikation des ursprünglichen Algorithmus behoben werden, indem man als Rekurrenzgleichung

$x_n=(b-1)-[(a{x}_{n-1}+c_{n-1})modb]$

verwendet.

Initialisierung

Die Initialisierung des Zustandsregisters sollte mit möglichst zufälligen und gleich verteilten Bits erfolgen, sprich etwa so viele 1- wie 0-Bits. Anderenfalls braucht der Generator eine „Warmlauf-Phase“, d. h. es muss eine gewisse Menge an Zufallszahlen generiert werden bis der Generator gleich verteilte Zufallszahlen liefert.

Implementierung

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];
}

Siehe auch

• Liste von Zufallszahlengeneratoren

Literatur

• Vorlage:Literatur
• Vorlage:Literatur

Weblinks

• Bibliothek mit statistischen Tests: 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