Multiply-with-carry
# 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

* Extrem lange Periode $(2^{131086}$ für den CMWC mit 16 kB Zustandsregister).
* Liefert gleichverteilte Bit-Sequenz.

### Algorithmus

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

    $x_{n}=(ax_{n-1}+c_{n-1})\mod b$
    $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 $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})\mod 10$
    $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 $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 $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)-[(ax_{n-1}+c_{n-1})\mod b]$

verwendet.

## Initialisierung

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

