Multiply-with-carry

aus Wikipedia, der freien Enzyklopädie
Wechseln zu: Navigation, Suche
Dieser Artikel oder Abschnitt bedarf einer Überarbeitung. Näheres ist auf der Diskussionsseite angegeben. Hilf mit, ihn zu verbessern, und entferne anschließend diese Markierung.

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[Bearbeiten]

  1. Extrem lange Periode (2131086 für den CMWC mit 16 kB Zustandsregister).
  2. Liefert gleichverteilte Bit-Sequenz.

Algorithmus[Bearbeiten]

Der Algorithmus für den MWC ist recht simpel und kann durch zwei Rekurrenzgleichungen beschrieben werden:

x_n = ( a x_{n-1} + c_{n-1} ) \mod b
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[Bearbeiten]

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 = ( 6 x_{n-1} + c_{n-1} ) \mod 10
c_n = \lfloor ( 6 x_{n-1} + c_{n-1} ) / 10 \rfloor
n ( 6 x_{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[Bearbeiten]

Um eine maximale Periodenlänge zu erhalten, wird z. B. bei Verwendung von 32-Bit-Integern für 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 durch eine kleine Modifikation des ursprünglichen Algorithmus behoben werden, indem man als Rekurrenzgleichung

x_n = (b-1) - [ a x_{n-1} + c \mod b ]

verwendet.

Initialisierung[Bearbeiten]

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.

Implementierung[Bearbeiten]

MWC[Bearbeiten]

#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[Bearbeiten]

#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[Bearbeiten]

Weblinks[Bearbeiten]