Robert Sedgewick: Algorithmen

[ Inhaltsverzeichnis ] [ vorhergehende Seite ] [ nächste Seite ] [ Stichwort ]


35. Zufallszahlen



Methode der additiven Kongruenz

Ein anderes Verfahren für die Erzeugung von Zufallszahlen beruht auf den Schieberegistern mit linearer Rückführung, die für ältere Verschlüsselungsmaschinen verwendet wurden. Die Idee besteht darin, mit einem Register zu beginnen, das mit einem beliebigen Muster gefüllt ist (nicht alles Nullen), und es dann (zum Beispiel) um einen Schritt nach rechts zu verschieben, wobei die links freigewordene Positione mit einem Bit gefüllt wird, das auf der Grundlage des Registerinhalts bestimmt wird.

Abbildung 35.1 zeigt ein einfaches, vier Bits umfassendes Schieberegister mit linearer Rückführung, wobei das neue Bit durch die XOR-Verknüpfung der beiden am weitesten rechts befindlichen Bits gebildet wird. Wenn das Register zum Beispiel am Anfang mit dem Muster 1111 gefüllt ist, enthält es nach einem Schritt 0111: Die Bits 111 werden um eine Stelle nach rechts verschoben, und das Bit ganz links erhält den Wert 0, da die beiden ganz rechts befindlichen Bits übereinstimmen. Wenn man dies fortsetzt, lauten die Inhalte des Registers in den aufeinanderfolgenden Schritten 0011, 0001, 1000, 0100, 0010, 1001, 1100, 0110, 1011, 0101, 1010, 1101, 1110, 1111. Nachdem wir wieder beim Anfangsmuster angelangt sind, verläuft der Prozeß offensichtlich zyklisch.

Abbildung 35.1
Abbildung 35.1 Ein aus vier Bits bestehendes Schieberegister mit linearer Rückführung.

Beachten Sie, daß alle möglichen von 0000 verschiedenen Bitmuster auftreten: Der Anfangswert wiederholt sich nach 15 Schritten. Wenn wir jedoch als »Abgriffs«-Positionen (Bits, die für die Rückführung verwendet werden) 0 und 2 (wenn wir sie von rechts numerieren) anstelle von 0 und 1 benutzen, erhalten wir die Folge 1111, 0111, 0011, 1001, 1100, 1110, 1111 und somit nicht den vollständigen Zyklus. Wir möchten jedoch garantieren, daß wir immer einen vollständigen Zyklus erhalten.

Im allgemeinen ist es für n Bits umfassende Schieberegister mit linearer Rückführung möglich, es so einzurichten, daß die Länge des Zyklus 2n - 1 beträgt. Daher ergeben solche Register für große n gute Zufallszahlengeneratoren. Beispielsweise könnte man n = 31 oder n = 63 verwenden. Wie bei der Methode der linearen Kongruenz sind die mathematischen Eigenschaften dieser Register gründlich untersucht worden. Zum Beispiel ist viel über die Wahl der »Abgriffs«-Positionen bekannt, die für Register von verschiedener Größe zur Erzeugung aller Bitmuster führen. Für n = 31 etwa würde den Abgriff der Positionen 0 und entweder 4, 7, 8, 14, 19, 25, 26 oder 29 zum Ziel führen.

Die aufeinanderfolgenden Registerinhalte sind als zufällige Folge nicht brauchbar, da in jedem aufeinanderfolgenden Paar alle Bits außer einem übereinstimmen. Vielmehr sollte man sich dies als eine Vorrichtung zur Erzeugung einer Folge zufälliger Bits vorstellen (das am weitesten links befindliche Bit des Registers), in unserem Beispiel 100010011010111. Wie in Kapitel 23 erwähnt wurde, sind solche Vorrichtungen in der Kryptographie von Nutzen, da sie aus kleinen Schlüsseln lange Bitfolgen erzeugen können.

Eine weitere interessante Tatsache ist, daß die Berechnung mit der gleichen Rekursionsformel wortweise anstatt bitweise ausgeführt werden kann. Wenn wir in unserem Beispiel zwei aufeinanderfolgende Worte bitweise XOR-verknüpfen, erhalten wir das Wort, das in der Liste drei Plätze später erscheint. Dies führt uns zu einem Zufallszahlengenerator, der sich auf einem Universalrechner leicht implementieren läßt. Die Verwendung eines Schieberegisters mit Rückführung mit Abgriff der Bits b und c entspricht der Anwendung der Rekursion a[k] = (a[k - b] + a[k - c]) mod m. Um den Zusammenhang mit dem Schieberegistermodell zu gewährleisten, sollte das »+« in dieser Rekursionsformel ein bitweises XOR sein. Es wurde jedoch gezeigt, daß sogar dann gute Zufallszahlen erzeugt werden dürften, wenn normale ganzzahlige Addition benutzt wird. Dies wird die Methode der additiven Kongruenz genannt.

Das ganz rechts stehende Bit der Zahlen in einem Generator der additiven Kongruenz verhält sich genau so wie die Bits in dem entsprechenden Schieberegister mit linearer Rückführung, so daß die Anzahl der Schritte, die ausgeführt werden, bevor sich das Verfahren zu wiederholen beginnt, wenigstens ebenso groß ist wie die Länge des Zyklus. Über diese Tatsache hinaus sind bezüglich der von solchen Generatoren erzeugten Zahlen nur wenige Ergebnisse erzielt worden; was für sie spricht, sind vor allem empirische Aussagen (sie genügen den statistischen Tests).

Um einen Generator der additiven Kongruenz zu implementieren, müssen wir eine Tabelle der Größe c führen, welche stets die letzten c erzeugten Zahlen enthält. Die Berechnung erfolgt, indem eine der Zahlen in der Tabelle durch die Summe zweier anderer Zahlen in der Tabelle ersetzt wird. Am Anfang sollte die Tabelle mit Zahlen gefüllt werden, die weder zu klein noch zu groß sind. (Ein einfacher Weg, diese Zahlen zu erhalten, ist die Benutzung eines einfachen Generators der linearen Kongruenz!) Knuth empfiehlt, b = 31 und c = 55 zu wählen. Somit müssen wir die 55 zuletzt erzeugten Zahlen registrieren. Die geeignete Datenstruktur hierfür ist eine Warteschlange (siehe Kapitel 3), doch da die Größe fest ist, verwenden wir einfach ein Feld dieser Größe, das mittels eines »zyklischen« Zeigers indiziert wird, wie in der folgenden Implementation:

    procedure randinit(s: integer);
      begin
      a[0]:=s; j:=0;
      repeat j:=j+1; a[j]:=(mult(b,a[j-1])+1) mod m until j=54;
      end;
    function randomint(r: integer): integer;
      begin
      j:=(j+1) mod 55;
      a[j]:=(a[(j+23) mod 55]+a[(j+54) mod 55]) mod m;
      randomint:=((a[j] div m1)*r) div m1
      end;

Die globale Variable a wurde durch eine vollständige Tabelle sowie einen auf sie weisenden Zeiger (j) ersetzt. Dieser große »globale Zustand« ist bei manchen Anwendungen ein Nachteil dieses Generators, doch er ist gleichzeitig ein Vorteil, da er zu einem extrem langen Zyklus führt (mindestens 255 - 1, selbst dann, wenn m klein ist).

Die Funktion randomint gibt eine zufällige ganze Zahl zwischen 0 und r - 1 zurück. Natürlich kann sie genauso wie oben leicht in eine Funktion umgewandelt werden, die eine zufällige reelle Zahl zwischen 0 und 1 zurückgibt (a[j]/m).


[ Inhaltsverzeichnis ] [ vorhergehende Seite ] [ nächste Seite ] [ Stichwort ]