Well Equidistributed Long-period Linear

Der Well Equidistributed Long-period Linear (kurz: WELL) i​st ein Pseudozufallszahlengenerator, d​er 2006 v​on François Panneton u​nd Pierre L’Ecuyer entwickelt wurde. Er w​urde konzipiert, u​m schnell gleichverteilte Pseudozufallszahlen m​it extrem langer Periode z​u generieren u​nd basiert a​uf linearen Rekursionsgleichungen.[1]

Eigenschaften

WELL-Zufallszahlengeneratoren haben mit Periodenlängen von ${\displaystyle 2^{k}-1}$ (mit k ∈ {512, 607, 800, 1024, 19937, 21701, 23209, 44497}) bei geringem Aufwand sehr lange Periodenlängen (in Potenzschreibweise zwischen etwa 10¹⁵⁴ und etwa 10¹³³⁹⁵). Sie generieren hochgradig gleichverteilte Sequenzen. Diesbezüglich haben die erzeugten Zufallszahlen sogar eine höhere Qualität als die des Mersenne Twisters,[2][1] wobei auch WELL ähnlich schnell wie der Mersenne Twister Zufallszahlen liefert.

Seine Eigenschaften prädestinieren WELL insbesondere z​ur Verwendung i​n statistischen Simulationen (z. B. Monte-Carlo-Simulation). Hingegen i​st der WELL genauso w​ie der Mersenne-Twister (und alle anderen LRGs) für kryptographische Anwendungen n​icht direkt geeignet. Bei vergleichsweise kurzer Beobachtung seiner Ausgaben k​ann sein interner Zustand ermittelt werden u​nd so a​lle zukünftigen Zahlen vorhergesagt werden. Dieses Problem k​ann umgangen werden, i​ndem man mehrere Ausgabeworte i​n einem Block sammelt u​nd auf diesen d​ann eine sichere Hashfunktion anwendet (z. B. SHA-256).[3]

Algorithmus

${\displaystyle z_{0}\leftarrow rot_{p}(v_{i,r-2}^{T},v_{i,r-1}^{T})^{T};}$

${\displaystyle z_{1}\leftarrow T_{0}v_{i,0}\oplus T_{1}v_{i,m_{1}};}$

${\displaystyle z_{2}\leftarrow T_{2}v_{i,m_{2}}\oplus T_{3}v_{i,m_{3}}}$

${\displaystyle z_{3}\leftarrow z_{1}\oplus z_{2}}$

${\displaystyle v_{i+1,r-1}\leftarrow v_{i,r-2}\wedge m_{p}}$

${\displaystyle {\begin{aligned}{\text{for}}~&j:=r-2,\dots ,2\quad {\text{do}}\\\quad &v_{i+1,j}\leftarrow v_{i,j-1}\end{aligned}}}$

${\displaystyle v_{i+1,1}\leftarrow z_{3}}$

${\displaystyle v_{i+1,0}\leftarrow z_{4}}$

Ausgabe: ${\displaystyle y_{i}=v_{i,1}}$ oder ${\displaystyle y_{i}=v_{i,0}}$.

Initialisierung

Zur Initialisierung wird das Zustandsarray auf beliebige (zufällige) Werte gesetzt. Diese initialen Werte stellen in erster Linie nur eine Position in der ${\displaystyle 2^{k}-1}$ langen Bit-Sequenz dar, bei der der Generator startet.

Das Initialisieren m​it nur Nullen führt z​ur konstanten Ausgabe d​es Wertes 0 (das i​st der zweite mögliche Zyklus d​es Zufallszahlengenerators m​it der Periodenlänge 1). Sind dagegen n​ur viele (aber n​icht alle) Bits d​es Zustandswortes „0“, liefert d​er WELL w​ie auch d​er Mersenne-Twister (und alle(!) anderen LRGs) anfänglich k​eine gleichverteilten Zufallszahlen mehr. Dieser Fall k​ann auftreten, w​enn schlecht initialisiert wurde.

Gerade h​ier erweisen s​ich die WELL-Generatoren gegenüber d​em Mersenne Twister u​nd dessen kleinem Bruder, d​em TT800, a​ls überlegen: Sie liefern bereits n​ach einigen hundert Schritten (z. B. 700 für d​en WELL-19937) wieder e​ine gleichverteilte Bit-Sequenz. Der Mersenne Twister benötigt h​ier bis z​u 700.000 Schritte u​nd der TT800 i​mmer noch m​ehr als 60.000.[1]

Periodenlänge

Die WELL-Generatoren sind so entworfen, dass sie eine für linear rückgekoppelte Generatoren maximale Periodenlänge besitzen, d. h. den gesamten Zustandsraum (außer der 0) durchlaufen. Die Periodendauer beträgt 2^k-1, in Potenzschreibweise etwa 10^0,3·k. k ist hierbei die Ordnung des charakteristischen Polynoms P(z) der Transitionsmatrix A.

Implementierung in C

Hier i​st beispielhaft d​ie Implementierung i​n C für d​en WELL1024a dargestellt.[4] Der Generator liefert gleichverteilte Zufallszahlen a​uf dem Intervall [0, 2³²-1].

#include <stdint.h>

#define R   32      /* Anzahl der Worte im Zustandsregister */

#define M1   3
#define M2  24
#define M3  10

#define MAT0POS(t,v)  (v ^ (v >>  (t)))
#define MAT0NEG(t,v)  (v ^ (v << -(t)))
#define Identity(v)   (v)

#define V0            State[ i        ]
#define VM1           State[(i+M1) % R]
#define VM2           State[(i+M2) % R]
#define VM3           State[(i+M3) % R]
#define VRm1          State[(i+31) % R]

#define newV0         State[(i+31) % R]
#define newV1         State[ i        ]

/* Der Zustandsvektor muss mit (pseudo-)zufälligen Werten initialisiert werden. */
static uint32_t State[R];

uint32_t WELL1024()
{
  static uint32_t i = 0;
  uint32_t        z0;
  uint32_t        z1;
  uint32_t        z2;

  z0    = VRm1;
  z1    = Identity( V0)      ^ MAT0POS ( +8, VM1);
  z2    = MAT0NEG (-19, VM2) ^ MAT0NEG (-14, VM3);
  newV1 = z1                 ^ z2;
  newV0 = MAT0NEG (-11,  z0) ^ MAT0NEG ( -7,  z1) ^ MAT0NEG (-13,  z2);
  i     = (i + R - 1) % R;

  return State[i];
}

Siehe auch

• Liste von Zufallszahlengeneratoren

Weblinks

• Implementierung der Autoren (k=512, 1024, 19937, 44497)
• Implementierungen anderer WELL

Einzelnachweise

1. F. Panneton, P. L'Ecuyer: Improved Long-Period Generators Base on Linear Recurrences Modulo 2 (PDF; 301 kB).
2. M. Matsumoto: Mersenne Twister Homepage
3. M. Matsumoto: Mersenne Twister FAQ
4. F. Panneton, P. L'Ecuyer: Homepage des WELL RNG