Arithmetischer Zufallszahlengenerator - LinkFang.de





Arithmetischer Zufallszahlengenerator


Arithmetische Zufallszahlengeneratoren sind Zufallszahlengeneratoren zur Erzeugung von Zufallszahlen, die auf der Arithmetik beruhen. Sie basieren auf dem Satz von Weyl, verwenden

[math]u_i = i y_0 - \lfloor i y_0 \rfloor = i y_0 \, \mod \, 1[/math]

als Generator, wobei die Definitionen bei Satz von Weyl gelten, also insbesondere [math]y_0 \in ]0, 1[[/math] eine irrationale Zahl ist. Hierbei steht [math]\mod[/math] für die Modulo-Operation. [math]\lfloor a \rfloor[/math] bezeichnet die größte Ganzzahl die kleiner oder gleich [math]a[/math] ist.

Arithmetische Zufallszahlengenerator werden in der Praxis statt physikalischer Zufallszahlengeneratoren eingesetzt. Da auf Taschenrechnern oder Computern keine irrationalen Zahlen darstellbar sind, beschränkt man sich häufig auf rekursive arithmetische Zufallszahlengeneratoren.

Rekursive arithmetische Zufallszahlengeneratoren

Dies sind Zufallszahlengeneratoren, die auf arithmetischen Zufallszahlengeneratoren basieren, bei denen man sich jedoch mit bestimmten rationalen Zahlen als Zufallszahlen zufriedengibt, da irrationale Zahlen, von denen arithmetische Zufallszahlengeneratoren ausgehen, auf Rechnern nicht darstellbar sind. Es handelt sich also um Pseudozufallszahlengeneratoren.

Zur Initialisierung des Generators verwendet man Startwerte [math]y_0, y_1, ..., y_{k-1}\,[/math], die als Saat bezeichnet werden. Sie können z. B. fest vorgegeben werden, wenn die erzeugte Zahlenfolge wiederholbar sein soll, oder man initialisiert sie auf zufällige Weise. Häufig verwendet man dafür die Rechneruhr als Datenquelle, die aktuelle Uhrzeit bestimmt also die Initialwerte der [math]y_n\,[/math].

Eine arithmetische Funktion

[math]f : \left\{ 0, ..., m-1 \right\}^k \rightarrow \left\{ 0, ..., m-1 \right\}[/math]

erzeugt nun sukzessive die Werte

[math]y_n := f ( y_{n-k}, y_{n-k+1}, ..., y_{n-1} )\,[/math], wobei [math]n \ge k[/math].

Als Zufallszahlen im Intervall [math][0; 1[[/math] verwendet man dann z. B.:

[math]u_i := \frac{y_i}{m}[/math].

Man gibt sich für die Zufallszahlen also mit Werten aus der Menge [math]\left\{ 0, \frac{1}{m}, \frac{2}{m}, ..., \frac{m-1}{m} \right\}[/math] zufrieden, wobei [math]m[/math] eine hinreichend große natürliche Zahl ist.

Die wohl bedeutendsten rekursiven arithmetischen Zufallszahlengeneratoren sind Kongruenzgeneratoren.

Vorteile

Bei geeigneter Funktion  [math]f[/math]  lassen sich schnell Zufallszahlen erzeugen. Diese sind bei Angabe der Saat vollständig reproduzierbar.

Nachteile

Die Folge [math](y_n)_{n \ge 0}[/math] ist deterministisch. Es werden keine echten Zufallszahlen, sondern vielmehr nur Pseudozufallszahlen erzeugt. Es handelt sich also um einen Pseudozufallszahlengenerator. Die Determiniertheit bedingt auch, dass eine Unabhängigkeit und Gleichverteilung der Folge nicht gegeben ist. Insbesondere wird irgendwann eine Schleife erzeugt. Es gibt also [math]n_0, p \in \mathbb{N}[/math] mit [math]y_{n+p} = y_n\,[/math] für alle [math]n \ge n_0[/math]. Das kleinste [math]p[/math] bezeichnet man hierbei als Periode.

Ob diese Nachteile aber eine Rolle spielen, hängt von der Anwendung ab: Zum Beispiel ist es für Simulationen kein Nachteil, dass die generierten Zahlen vorhersagbar sind, solange die Periodenlänge hinreichend groß ist. Im Gegenteil: Die Reproduzierbarkeit der Zahlen erleichtert die Analyse und Fehlersuche.

Literatur


Kategorien: Pseudozufallszahlengenerator | Zahlentheorie

Quelle: Wikipedia - http://de.wikipedia.org/wiki/Arithmetischer Zufallszahlengenerator (Vollständige Liste der Autoren des Textes [Versionsgeschichte])    Lizenz: CC-by-sa-3.0

Änderungen: Alle Bilder mit den meisten Bildunterschriften wurden entfernt. Ebenso alle zu nicht-existierenden Artikeln/Kategorien gehenden internen Wikipedia-Links (Bsp. Portal-Links, Redlinks, Bearbeiten-Links). Entfernung von Navigationsframes, Geo & Normdaten, Mediadateien, gesprochene Versionen, z.T. ID&Class-Namen, Style von Div-Containern, Metadaten, Vorlagen, wie lesenwerte Artikel. Ansonsten sind keine Inhaltsänderungen vorgenommen worden. Weiterhin kann es durch die maschinelle Bearbeitung des Inhalts zu Fehlern gerade in der Darstellung kommen. Darum würden wir jeden Besucher unserer Seite darum bitten uns diese Fehler über den Support mittels einer Nachricht mit Link zu melden. Vielen Dank!

Stand der Informationen: August 201& - Wichtiger Hinweis: Da die Inhalte maschinell von Wikipedia übernommen wurden, ist eine manuelle Überprüfung nicht möglich. Somit garantiert LinkFang.de nicht die Richtigkeit und Aktualität der übernommenen Inhalte. Sollten die Informationen mittlerweile fehlerhaft sein, bitten wir Sie darum uns per Support oder E-Mail zu kontaktieren. Wir werden uns dann innerhalb von spätestens 10 Tagen um Ihr Anliegen kümmern. Auch ohne Anliegen erfolgt mindestens alle drei Monate ein Update der gesamten Inhalte.