Arithmetischer Zufallszahlengenerator

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

u_i = i y_0 - \lfloor i y_0 \rfloor = i y_0 \, \mod \, 1

als Generator, wobei die Definitionen bei Satz von Weyl gelten, also insbesondere y_0 \in ]0, 1[ eine irrationale Zahl ist. Hierbei steht \mod für die Modulo-Operation. \lfloor a \rfloor bezeichnet die größte Ganzzahl die kleiner oder gleich a 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 zufrieden gibt, 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 y_0, y_1, ..., y_{k-1}\,, 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 y_n\,.

Eine arithmetische Funktion

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

erzeugt nun sukzessive die Werte

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

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

u_i := \frac{y_i}{m}.

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

Die wohl bedeutendsten rekursiven arithmetischen Zufallszahlengeneratoren sind Kongruenzgeneratoren.

Vorteile

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

Nachteile

Die Folge (y_n)_{n \ge 0} 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 n_0, p \in \mathbb{N} mit y_{n+p} = y_n\, für alle n \ge n_0. Das kleinste p 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.



Wikimedia Foundation.

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

  • Rekursiver arithmetischer Zufallszahlengenerator — Arithmetische Zufallszahlengeneratoren sind Zufallszahlengeneratoren zur Erzeugung von Zufallszahlen, die auf der Arithmetik beruhen. Sie basieren auf dem Satz von Weyl, verwenden also als Generator, wobei die Definitionen bei Satz von Weyl… …   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

  • Physikalischer Zufallszahlengenerator — Zufallszahlengenerator fehlen folgende wichtige Informationen: Güte wird nur mangelhaft behandelt Überschneidung mit spezielleren Artikeln sind zu dürftig oder zu ausschweifend Hard und Softwaretechnische Realisierung ist sehr dürftig Du kannst… …   Deutsch Wikipedia

  • Hardwarezufallszahlengenerator — Zufallszahlengenerator fehlen folgende wichtige Informationen: Güte wird nur mangelhaft behandelt Überschneidung mit spezielleren Artikeln sind zu dürftig oder zu ausschweifend Hard und Softwaretechnische Realisierung ist sehr dürftig Du kannst… …   Deutsch Wikipedia

  • Pseudozufallszahlengenerator — Zufallszahlengenerator fehlen folgende wichtige Informationen: Güte wird nur mangelhaft behandelt Überschneidung mit spezielleren Artikeln sind zu dürftig oder zu ausschweifend Hard und Softwaretechnische Realisierung ist sehr dürftig Du kannst… …   Deutsch Wikipedia

  • Zufallsgenerator — Zufallszahlengenerator fehlen folgende wichtige Informationen: Güte wird nur mangelhaft behandelt Überschneidung mit spezielleren Artikeln sind zu dürftig oder zu ausschweifend Hard und Softwaretechnische Realisierung ist sehr dürftig Du kannst… …   Deutsch Wikipedia

  • Zufallszahlgenerator — Zufallszahlengenerator fehlen folgende wichtige Informationen: Güte wird nur mangelhaft behandelt Überschneidung mit spezielleren Artikeln sind zu dürftig oder zu ausschweifend Hard und Softwaretechnische Realisierung ist sehr dürftig Du kannst… …   Deutsch Wikipedia

  • Allgemeiner Kongruenzgenerator — Die Kongruenzgeneratoren bilden eine Klasse von Algorithmen, die zufällig aussehende Zahlenfolgen erzeugen. Die dadurch erzeugten Zahlen nennt man Pseudozufallszahlen, da sie deterministisch erzeugt werden und somit nicht wirklich zufällig sind.… …   Deutsch Wikipedia

  • Fibonacci-Generator — Die Kongruenzgeneratoren bilden eine Klasse von Algorithmen, die zufällig aussehende Zahlenfolgen erzeugen. Die dadurch erzeugten Zahlen nennt man Pseudozufallszahlen, da sie deterministisch erzeugt werden und somit nicht wirklich zufällig sind.… …   Deutsch Wikipedia

  • Fibonacci-Kongruenzgenerator — Die Kongruenzgeneratoren bilden eine Klasse von Algorithmen, die zufällig aussehende Zahlenfolgen erzeugen. Die dadurch erzeugten Zahlen nennt man Pseudozufallszahlen, da sie deterministisch erzeugt werden und somit nicht wirklich zufällig sind.… …   Deutsch Wikipedia

Share the article and excerpts

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