Multiply-with-carry

aus Wikipedia, der freien Enzyklopädie
Zur Navigation springen Zur Suche springen

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.

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

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

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

Hier steht 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 eine Primzahl ist. Dann gibt der Generator für alle nicht-trivialen Startwerte und eine Sequenz mit der Periodenlänge aus.

Sei , und als Startwerte , :

Sequenzlänge:

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 aus.

Complimentary Multiply-with-carry

[Bearbeiten | Quelltext bearbeiten]

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

verwendet.

Initialisierung

[Bearbeiten | Quelltext bearbeiten]

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 müssen eine gewisse Menge Zufallszahlen generiert werden, bis der Generator gleich verteilte Zufallszahlen liefert.

Implementierung

[Bearbeiten | Quelltext 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);
}
#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];
}
  • 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]).