Mersenne-Twister

aus Wikipedia, der freien Enzyklopädie
Wechseln zu: Navigation, Suche

Der Mersenne-Twister ist ein Pseudozufallszahlengenerator, der 1997 von Makoto Matsumoto und Takuji Nishimura entwickelt wurde. Er generiert Sequenzen von Pseudozufallszahlen und wurde darauf zugeschnitten, die Probleme älterer Algorithmen zu überwinden (wie z. B. linearer Kongruenzgeneratoren).

Es gibt zwei Varianten dieses Algorithmus; die neuere und verbreitetere ist der Mersenne-Twister „MT 19937“, der hier beschrieben wird.

Eigenschaften[Bearbeiten]

  1. Er hat die extrem lange Periode von 219937−1 (≈ 4,3·106001). Diese Periodenlänge erklärt auch den Namen des Algorithmus: Sie ist eine Mersenne-Primzahl, und einige Eigenschaften des Algorithmus resultieren daraus.
  2. Alle Bits der Ausgabesequenz sind gleichverteilt. Somit sind die zurückgelieferten Integer-Werte ebenfalls hochgradig gleichverteilt (bis zur Dimension 623, siehe unten). Daraus folgt eine extrem geringe Korrelation zwischen aufeinanderfolgenden Wertefolgen der Ausgabesequenz.
  3. Der Algorithmus ist schnell. Er generiert immer 624 neue Zustandswörter auf einmal, was sich auf heutigen SIMD-Architekturen ebenfalls positiv auf die Geschwindigkeit auswirken kann.

Andererseits hat er den Nachteil, auf einer großen Datenmenge von etwa 2,5 kByte (624 Wörter mit je 32 Bits) zu arbeiten. Das kann bei Rechnerarchitekturen mit relativ kleinem Cache und langsamerem Arbeitsspeicher einen Geschwindigkeitsnachteil ergeben.

Das Wort „Twister“ bezieht sich auf eine bestimmte Transformation des Algorithmus, durch die diese hochgradige Gleichverteilung sichergestellt wird (Reine lineare Kongruenzgeneratoren können mit vertretbarem Aufwand nur fünfdimensionale Gleichverteilung garantieren).

Eine n-dimensionale Gleichverteilung heißt: teilt man die Ausgabesequenz in Tupel von je n Zahlen, dann ist die Sequenz der n-Tupel gleichverteilt im n-dimensionalen Raum.

Im Gegensatz zu anderen Algorithmen ist der Mersenne-Twister in seiner Reinform nicht für kryptographische Anwendungen geeignet. Für viele andere Anwendungen wird er aber bereits erfolgreich verwendet.

Algorithmus[Bearbeiten]

Die Werte  Y_1 bis  Y_N (mit  N = 624 ) werden als Startwerte vorgegeben. Die weiteren Werte  Y_i mit  i > N werden folgendermaßen berechnet:

 h := Y_{i-N} - Y_{i-N} \, \bmod \, 2^{31} + Y_{i-N+1} \, \bmod \, 2^{31}
 Y_i := Y_{i-227} \oplus \lfloor h/2 \rfloor \oplus ((h \, \bmod \, 2) \cdot 9908b0df_{hex})

Das Symbol  \oplus bezeichnet die bitweise XOR-Verknüpfung, und „hex“ steht für hexadezimal. Das Symbol  \lfloor . \rfloor ist die Gaußklammer und steht für den abgerundeten Wert, d. h. die größte Ganzzahl, die nicht größer als das Argument in der Klammer ist.

Um die 623-dimensionale Gleichverteilung für alle 32 Bits der  Y_i sicherzustellen, werden die Y_i noch modifiziert:

 x := Y_i \oplus \lfloor Y_i / 2^{11} \rfloor
 y := x \oplus ((x \cdot 2^7) \, \and \, 9d2c5680_{hex})
 z := y \oplus ((y \sdot 2^{15}) \, \and \, efc60000_{hex})
 Z_i := z \oplus \lfloor z / 2^{18} \rfloor

Dabei steht  \and für die bitweise UND-Verknüpfung.

Die so berechneten Z_i werden als Zufallszahlen verwendet.

Initialisierung[Bearbeiten]

Als Startwerte Y_1 bis Y_N wählt man im Idealfall echte Zufallszahlen, die z.B. durch einen physikalischen Zufallszahlengenerator erzeugt werden können. Es können aber auch Pseudozufallszahlen von einem anderen Generator verwendet werden.

Es dürfen nicht alle Bits, die den Zustand des Mersenne-Twisters ausmachen, mit Null initialisiert werden, denn sonst erzeugt er immer nur Null als „Zufallszahl“. Dies sind das höchstwertige Bit in Y_1 sowie alle Bits in den übrigen Variablen Y_2 bis Y_N.

Je weniger zufällig die Startwerte sind (d. h. je ungleicher die Bits verteilt sind), umso länger ist die „Aufwärmphase“, die der Mersenne-Twister braucht, bis er gute Pseudozufallszahlen ausgibt. Die schlechtest mögliche Initialisierung besteht aus nur einem einzigen 1er-Bit und sonst lauter Nullen. Hiernach benötigt der Mersenne-Twister über 700.000 Aufrufe, bis er wieder eine gleichverteilte Bitsequenz liefert.[1] Im Zweifelsfall sollte man also etwa 800.000 Zufallszahlen generieren lassen, bevor man die Zahlen verwendet. Alternativ existieren auch moderne Generatoren, die wesentlich kürzere Erholungszeiten besitzen, wie z. B. der WELL oder Marsaglias Xorshift.

Allerdings kann man sich auf diese Weise auch die Initialisierung mit einem weiteren PRNG sparen (falls man diesem bspw. nicht traut): Man setzt Y_2 (im Code y[1]) auf einen zufälligen Seed-Wert (z. B. die Uhrzeit) und alle weitere Y_N auf 0 (im C-Code sind sie das i. d. R. wegen des static-Attributs bereits). Anschließend ruft man den Generator einfach 800.000 mal auf.

Code[Bearbeiten]

Diese Berechnungen lassen sich z. B. in C-Code effizient implementieren. Die folgende Funktion berechnet immer N = 624 Wörter auf einmal, und danach werden diese aus dem Vektor y der Reihe nach ausgelesen:

#include <stdint.h>
 
uint32_t mersenne_twister() {
#define N     624
#define M     397
#define HI    0x80000000
#define LO    0x7fffffff
  static const uint32_t A[2] = { 0, 0x9908b0df };
  static uint32_t y[N];
  static int index = N+1;
  static const uint32_t seed = 5489UL;
  uint32_t  e;
 
  if (index > N) {
    int i;
    /* Initialisiere y mit Pseudozufallszahlen */
    y[0] = seed;
 
    for (i=1; i<N; ++i) {
      y[i] = (1812433253UL * (y[i-1] ^ (y[i-1] >> 30)) + i);
      /* See Knuth TAOCP Vol2. 3rd Ed. P.106 for multiplier. */
      /* In the previous versions, MSBs of the seed affect   */
      /* only MSBs of the array mt[].                        */
      /* 2002/01/09 modified by Makoto Matsumoto             */
    }
  }
 
  if (index >= N) {
    int i;
    /* Berechne neuen Zustandsvektor */
    uint32_t h;
 
    for (i=0; i<N-M; ++i) {
      h = (y[i] & HI) | (y[i+1] & LO);
      y[i] = y[i+M] ^ (h >> 1) ^ A[h & 1];
    }
    for ( ; i<N-1; ++i) {
      h = (y[i] & HI) | (y[i+1] & LO);
      y[i] = y[i+(M-N)] ^ (h >> 1) ^ A[h & 1];
    }
 
    h = (y[N-1] & HI) | (y[0] & LO);
    y[N-1] = y[M-1] ^ (h >> 1) ^ A[h & 1];
    index = 0;
  }
 
  e = y[index++];
  /* Tempering */
  e ^= (e >> 11);
  e ^= (e <<  7) & 0x9d2c5680;
  e ^= (e << 15) & 0xefc60000;
  e ^= (e >> 18);
 
  return e;
#undef N
#undef M
#undef HI
#undef LO
}

TT800[Bearbeiten]

Matsumoto und Nishimura entwickelten zuvor bereits einen „kleinen Bruder“ des Mersenne-Twisters mit der Bezeichnung TT800. Er arbeitet nach dem gleichen Funktionsprinzip, aber auf einer kleineren Datenmenge von nur 25 Wörtern, und sein Algorithmus ist ein wenig einfacher, weil zur Berechnung des jeweils nächsten Zustandswortes nicht drei, sondern nur zwei alte 32-bit-Zustandworte verrechnet werden. Seine Periodenlänge beträgt 2800-1 (≈ 6,7·10240).

#include <stdint.h>
 
uint32_t TT800() {
#define N  25
#define M   7
   static const uint32_t A[2] = { 0, 0x8ebfd028 };
   static uint32_t y[N];
   static int index = N+1;
   uint32_t  e;
 
   if (index >= N) {
     int k; 
     if (index > N) {
        unsigned r = 9, s = 3402;
        for (k=0; k<N; ++k) {
          r = 509845221 * r + 3;
          s *= s + 1;
          y[k] = s + (r >> 10);
        }
     }
     for (k=0; k<N-M; ++k)
        y[k] = y[k+M] ^ (y[k] >> 1) ^ A[y[k] & 1];
     for (; k<N; ++k)
        y[k] = y[k+(M-N)] ^ (y[k] >> 1) ^ A[y[k] & 1];
     index = 0;
   }
 
   e = y[index++];
  /* Tempering */
   e ^= (e <<  7) & 0x2b5b2500;
   e ^= (e << 15) & 0xdb8b0000;
   e ^= (e >> 16);
   return e;
#undef N
#undef M
}

Siehe auch[Bearbeiten]

Weblinks[Bearbeiten]

Literatur[Bearbeiten]

  • Makoto Matsumoto, Takuji Nishimura: Mersenne twister. A 623-dimensionally equidistributed uniform pseudorandom number generator. In: ACM Transactions on Modeling and Computer Simulation. 8, 1998, ISSN 1049-3301, S. 3–30.

Einzelnachweise[Bearbeiten]

  1. [1] (PDF; 301 kB)