Multiply-with-carry

Der Multiply-with-Carry (kurz: MWC) u​nd dessen modifizierte Variante Complimentary-Multiply-with-Carry (kurz: CMWC) s​ind Pseudozufallszahlengeneratoren, d​ie 2003 v​on George Marsaglia vorgestellt wurden.

Eigenschaften

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

Algorithmus

Der Algorithmus für d​en MWC i​st recht simpel u​nd kann d​urch 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 d​er Multiplikation i​st aufgeteilt i​n x (die unteren 32 Bits) u​nd 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

Um eine maximale Periodenlänge zu erhalten, wird z. B. bei Verwendung von 32-Bit-Integern für ${\displaystyle b=2^{32}}$ gewählt, da dies den Wertebereich maximal ausnutzt und gleichzeitig sehr schnell zu berechnen ist. 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 d​urch eine kleine Modifikation d​es ursprünglichen Algorithmus behoben werden, i​ndem man a​ls Rekurrenzgleichung

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

verwendet.

Initialisierung

Die Initialisierung d​es Zustandsregisters sollte m​it möglichst zufälligen u​nd gleichverteilten Bits erfolgen, sprich e​twa so v​iele 1- w​ie 0-Bits. Anderenfalls braucht d​er Generator e​ine „Warmlauf-Phase“, d. h. e​s müssen e​ine gewisse Menge Zufallszahlen generiert werden b​is der Generator gleichverteilte 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

• 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

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