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^131086 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:

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

${\displaystyle c_{n}=\lfloor (ax_{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 ${\displaystyle 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 ${\displaystyle m=ab-1}$ eine Primzahl ist. Dann gibt der Generator für alle nicht-trivialen Startwerte ${\displaystyle x_{1}}$ und ${\displaystyle c_{1}}$ eine Sequenz mit der Periodenlänge ${\displaystyle l=m-1}$ aus.

Beispiel

Sei ${\displaystyle a=6}$, ${\displaystyle b=10}$ und als Startwerte ${\displaystyle c_{1}=3}$, ${\displaystyle x_{1}=5}$:

Sequenzlänge: ${\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	21	2	1
4	8	0	8
5	48	4	8
6	52	5	2

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

Complimentary Multiply-with-carry

Für die Erzielung einer maximalen Periodenlänge wird beispielsweise bei Verwendung von 32-Bit-Integern für ${\displaystyle 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

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

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

• George Marsaglia: Random number generators. In: Journal of Modern Applied Statistical Methods. Band 2, Nr. 1, Mai 2003, S. 2–13, doi:10.22237/jmasm/1051747320 (englisch, archive.org [PDF; abgerufen am 29. Oktober 2022]). 
• George Marsaglia: On the Randomness of Pi and Other Decimal Expansions. Oktober 2005 (yaroslavvb.com [PDF; abgerufen am 25. November 2022]). 

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