Well Equidistributed Long-period Linear

Well Equidistributed Long-period Linear

Der Well Equidistributed Long-period Linear (kurz: WELL) ist ein Pseudozufallszahlengenerator, der 2006 von François Panneton und Pierre L’Ecuyer entwickelt wurde. Er wurde konzipiert, um schnell gleichverteilte Pseudozufallszahlen mit extrem langer Periode zu generieren und basiert auf linearen Rekursionsgleichungen.[1]

Inhaltsverzeichnis

Eigenschaften

WELL-Zufallszahlengeneratoren haben mit Periodenlängen von 2k − 1 (mit k ∈ {512, 607, 800, 1024, 19937, 21701, 23209, 44497}) bei geringem Aufwand sehr lange Periodenlängen (in Potenzschreibweise zwischen etwa 10154 und etwa 1013395). 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 zur Verwendung in statistischen Simulationen (z. B. Monte-Carlo-Simulation). Hingegen ist der WELL genauso wie der Mersenne-Twister (und alle anderen LRGs) für kryptographische Anwendungen nicht direkt geeignet. Bei vergleichsweise kurzer Beobachtung seiner Ausgaben kann sein interner Zustand ermittelt werden und so alle zukünftigen Zahlen vorhergesagt werden. Dieses Problem kann umgangen werden, indem man mehrere Ausgabeworte in einem Block sammelt und auf diesen dann eine sichere Hashfunktion anwendet (z. B. SHA-256)[3].

Algorithmus

z_0 \leftarrow rot_p ( v^T_{i,r-2}, v^T_{i,r-1} )^T;

z_1 \leftarrow T_0 v_{i,0} \oplus T_1 v_{i,m_1};

z_2 \leftarrow T_2 v_{i,m_2} \oplus T_3 v_{i,m_3}

z_3 \leftarrow z_1 \oplus z_2

v_{i+1,r-1} \leftarrow v_{i,r-2} AND m_p

\begin{align}
for &j := r-2, \dots, 2 \quad do \\
\quad & v_{i+1,j} \leftarrow v_{i,j-1}
\end{align}

v_{i+1,1} \leftarrow z_3

v_{i+1,0} \leftarrow z_4

Ausgabe: yi = vi,1 oder yi = vi,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 2k − 1 langen Bit-Sequenz dar, bei der der Generator startet.

Das Initialisieren mit nur Nullen führt zur konstanten Ausgabe des Wertes 0 (das ist der zweite mögliche Zyklus des Zufallszahlengenerators mit der Periodenlänge 1). Sind dagegen nur viele (aber nicht alle) Bits des Zustandswortes „0“, liefert der WELL wie auch der Mersenne-Twister (und alle(!) anderen LRGs) anfänglich keine gleichverteilten Zufallszahlen mehr. Dieser Fall kann auftreten, wenn schlecht initialisiert wurde.

Gerade hier erweisen sich die WELL-Generatoren gegenüber dem Mersenne Twister und dessen kleinem Bruder, dem TT800, als überlegen: Sie liefern bereits nach einigen hundert Schritten (z. B. 700 für den WELL-19937) wieder eine gleichverteilte Bit-Sequenz. Der Mersenne Twister benötigt hier bis zu 700.000 Schritte und der TT800 immer noch mehr 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 2k − 1, in Potenzschreibweise etwa 100,3·k. k ist hierbei die Ordnung des charakteristischen Polynoms P(z) der Transitionsmatrix A.

Implementierung in C

Hier ist beispielhaft die Implementierung in C für den WELL1024a dargestellt[4]:

#include <stdint.h>
 
#define W   32      /* Größe eines Wortes im des Zustandsregister in Bits (in diesem RNG nicht genutzt) */
#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        ]
 
static uint32_t State[R];
 
/* 
  Der Zufallszahlengenerator:
  - liefert gleichverteilte Zufallszahlen im Intervall [0 ... 2^32-1]
  - muss zuvor mindestens einmal mit WELL1024_Init() initialisiert werden
*/
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];
}
 
/*
   Initialisiert internen Zustand mit Pseudozufallszahlen (Marsaglia's 32-bit Xorshift RNG). 
   Als Argument muss ein Wert ungleich Null übergeben werden.
*/
void WELL1024_Init(uint32_t y)
{
  int i;
 
  for (i = 0; i < R; ++i)
  {
    y ^= y << 13;
    y ^= y >> 17;
    y ^= y <<  5;
    State[i] = y;
  }
}

Weblinks

Einzelnachweise

  1. a b c F. Panneton, P. L'Ecuyer: Improved Long-Period Generators Base on Linear Recurrences Modulo 2.
  2. M. Matsumoto: Mersenne Twister Homepage
  3. M. Matsumoto: Mersenne Twister FAQ
  4. F. Panneton, P. L'Ecuyer: Homepage des WELL RNG

Wikimedia Foundation.

Игры ⚽ Нужен реферат?

Schlagen Sie auch in anderen Wörterbüchern nach:

  • Well — bezeichnet eine Vertiefung in einer Mikrotiterplatte Well ist der Familienname folgender Personen: Günther van Well (1922–1993), deutscher Diplomat und Staatssekretär Roman Well (eigentlich Ruvelis Leiba Sobolevicius, später Robert Soblen;… …   Deutsch Wikipedia

  • Mersenne twister — The Mersenne twister is a pseudorandom number generator developed in 1997 by Makoto Matsumoto (松本 眞?) and Takuji Nishimura (西村 拓士?)[1] …   Wikipedia

  • Xorshift — Der Xorshift Generator ist eine Klasse moderner Pseudozufallszahlengeneratoren. Er generiert sehr schnell und einfach eine gleichverteilte Sequenz an Pseudozufallszahlen. Vorgestellt wurde der Xorshift Generator im Jahr 2003 von seinem Entwickler …   Deutsch Wikipedia

  • Zufallszahlengenerator — Als Zufallszahlengenerator, gelegentlich auch zu Zufallsgenerator verkürzt, bezeichnet man ein Verfahren, das eine Folge von Zufallszahlen erzeugt. Der Bereich, aus dem die Zufallszahlen erzeugt werden, hängt dabei vom speziellen… …   Deutsch Wikipedia

  • Pseudorandom number generator — A pseudorandom number generator (PRNG), also known as a deterministic random bit generator (DRBG),[1] is an algorithm for generating a sequence of numbers that approximates the properties of random numbers. The sequence is not truly random in… …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”