Robert Sedgewick: Algorithmen

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


35. Zufallszahlen



Bemerkungen zur Implementation

Um zu erreichen, daß ein Zufallszahlengenerator für eine große Anzahl von Anwendungen geeignet ist, wird gewöhnlich eine Reihe von zusätzlichen Vorkehrungen getroffen. Normalerweise ist es wünschenswert, den Generator als eine Funktion bereitzustellen, die initialisiert und dann wiederholt aufgerufen wird, wobei sie jedesmal eine andere Zufallszahl zurückgibt. Eine andere Möglichkeit ist, den Zufallszahlengenerator einmal aufzurufen und ihn ein Feld ausfüllen zu lassen, das alle Zufallszahlen enthält, die für eine bestimmte Berechnung benötigt werden. In beiden Fällen ist es wünschenswert, daß der Generator bei aufeinanderfolgenden Aufrufen die gleiche Folge erzeugt (für das Überprüfen am Anfang oder für den Vergleich von Programmen mit Hilfe der gleichen Eingabedaten), und daß er eine beliebige Folge erzeugt (für späteres Überprüfen). Alle diese Eigenschaften erfordern das Operieren mit dem »Status«, den der Zufallszahlengenerator zwischen den Aufrufen annimmt. In manchen Programmierumgebungen kann dies sehr mühsam sein. Der additive Generator hat den Nachteil, daß er einen relativ großen Status besitzt (das Feld der zuletzt erzeugten Wörter), hat jedoch den Vorteil, daß er einen derart langen Zyklus hat, daß es wahrscheinlich nicht notwendig ist, daß jeder Anwender ihn initialisiert.

Eine konservative Methode, sich vor Unregelmäßigkeiten in einem Zufallszahlengenerator zu schützen, ist die Kombination von zwei Generatoren. (Die Benutzung eines Generators der linearen Kongruenz zum Initialisieren der Tabelle für einen Generator der additiven Kongruenz ist ein elementares Beispiel dafür.) Eine einfache Methode, eine Kombination von Generatoren zu implementieren, besteht darin, den ersten Generator eine Tabelle ausfüllen und den zweiten zufällige Positionen in der Tabelle wählen zu lassen, um Zahlen für die Ausgabe zu liefern (und neue Zahlen vom ersten Generator zu speichern).

Beim Überprüfen eines Programms, das einen Zufallszahlengenerator verwendet, ist es gewöhnlich sinnvoll, zuerst einen trivialen oder entarteten Generator zu benutzen, einen Generator, der immer 0 oder aufeinanderfolgende zurückgibt.

In der Regel sind Zufallszahlengeneratoren empfindlich und müssen mit Vorsicht behandelt werden. Es ist schwer nachzuweisen, daß ein spezieller Generator gut ist, ohne einen enormen Aufwand in die verschiedenen statistischen Tests zu investieren. Die Lehre daraus ist: Man sollte sein Bestes tun, um einen guten Generator zu benutzen, auf der Grundlage der mathematischen Analyse und der Erfahrungen anderer; nur um sicherzugehen, sollte man die Zahlen untersuchen, um zu gewährleisten, daß sie zufällig »aussehen«; falls irgend etwas schiefgeht, suche man die Schuld beim Zufallszahlengenerator!


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