Zufallszahlengenerator

aus Wikipedia, der freien Enzyklopädie

Als Zufallszahlengenerator, gelegentlich auch zu Zufallsgenerator oder schlicht Generator 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 Zufallszahlengenerator ab. Es kann beispielsweise die Menge aller 32-Bit-Zahlen oder auch die Menge der reellen Zahlen im Intervall [0,1] sein. Meistens ist von einem Zufallszahlengenerator erwünscht, dass er gleichverteilte Werte aus dem jeweiligen Bereich erzeugt. Für gewisse statistische Simulationen sind auch solche Zufallszahlengeneratoren interessant, die eine vorgegebene Verteilung (z. B. Normalverteilung oder Poissonverteilung) erzeugen.

Inhaltsverzeichnis 1 Arten von Zufallszahlengeneratoren 1.1 Nichtdeterministische Zufallszahlengeneratoren 1.2 Deterministische Zufallszahlengeneratoren 1.2.1 Softwaretechnische Realisierungen 1.2.2 Hardwaretechnische Realisierungen 1.2.3 Sonstige Zufallszahlengeneratoren 2 Weblinks

[Bearbeiten] Arten von Zufallszahlengeneratoren

Man unterscheidet grundsätzlich zwischen nicht-deterministischen und deterministischen Zufallszahlengeneratoren. Nicht-deterministisch ist ein Zufallszahlengenerator dann, wenn er auch bei gleichen Ausgangsbedingungen unterschiedliche Werte liefert. Da die Implementierung einer Software-Prozedur immer deterministisch arbeitet, muss zur Realisierung eines nicht-deterministischen Zufallszahlengenerators ein externer, beispielsweise ein physikalischer, Vorgang einbezogen werden. Ein deterministischer Zufallszahlengenerator liefert bei gleichen Ausgangsbedingungen dagegen immer die gleiche Folge von Zufallszahlen (Pseudozufallszahlen). Die Erzeugung (deterministisch oder nicht-deterministisch) sagt allerdings noch nichts über die Güte der Zufallszahlen aus, also inwieweit sie statistischen Tests genügen. Dabei wird zum Beispiel überprüft, ob alle Werte in einem Intervall gleichmäßig auftauchen, ob gerade und ungerade Zahlen in etwa je zur 50% erzeugt werden, und so weiter. Da sich eine Pseudozufallszahlenfolge nach einiger Zeit wiederholt (man spricht von einem Zyklus), ist es erwünscht, dass man eine möglichst lange Folge von Zahlen erhält, bevor die Wiederholung einsetzt.

Oft werden beide Formen kombiniert, indem ein nicht-deterministischer Prozess den Startwert für einen deterministischen Zufallszahlengenerator liefert, wodurch die Nachteile beider Methoden umgangen werden.

[Bearbeiten] Nichtdeterministische Zufallszahlengeneratoren

• Physikalischer Zufallszahlengenerator: Ein Geigerzähler misst die Zahl der radioaktiven Zerfälle in einer bestimmten Zeitspanne. Man nutzt die Tatsache, dass radioaktive Isotope nach einer rein zufälligen Zeitspanne in das Tochterelement bzw. -isotop zerfallen. Die Zeitspanne hat aber beim gleichen Isotop immer den gleichen Mittelwert (die sogenannte Halbwertszeit). Da der radioaktive Zerfall unabhängig von Umgebungsbedingungen abläuft, kann dieser Vorgang Zufallszahlen hoher Güte liefern.

Bei physikalischen Zufallszahlengeneratoren gibt es allerdings das Problem der Alterung. Beispielsweise haben Geiger-Müller-Zählrohre eine Lebensdauer von typischerweise eine Billion Pulse und sind zudem abhängig von Temperatur, Magnetfeldern und der Versorgungsspannung. Zudem muss bei Geigerzählern die Pulsrate „deutlich höher“ als die Taktfrequenz sein, mit der die Pulse eingelesen werden. Eine Lösung dieses Problems ist viele mehr oder minder gute Zufallszahlengeneratoren zu nehmen und von diesen Zufallszahlen nur das letzte Bit zu verwenden um damit die Modulo-Zwei-Summe zu bilden. Nach dem zentralen Grenzwertsatz der Statistik erhält man damit auch mit schlechten Zufallszahlengeneratoren perfekt zufällige Zufallsbits, wenn man nur genügend viele Zufallszahlengeneratoren verwendet.

• Quasizufällige Ereignisse: Es wird beispielsweise die Systemzeit bestimmt, in der eine Benutzeraktion eintritt. Auf diese Weise erzeugte Zufallszahlen haben meist eine geringe Güte, lassen sich aber als Startwert für deterministische Verfahren verwenden.

• Hybrid-Generatoren: Pseudozufallszahlengeneratoren, die als Input einige wenige echte Zufallszahlen verwenden, also nicht nur Pseudozufallszahlen erzeugen. Ein Beispiel hierfür ist /dev/random unter Linux u. A.. Im einfachsten Fall wird einfach ein Pseudozufallszahlengenerator genommen, der gelegentlich mit einer neuen echten Zufallszahl als Startwert neu gestartet wird.

[Bearbeiten] Deterministische Zufallszahlengeneratoren

Deterministische Zufallszahlengeneratoren haben den Vorteil, dass die Zufallszahlen bei hinreichend genauer Dokumentation später reproduziert werden können. Diese Eigenschaft ist bedeutsam für die Anerkennung wissenschaftlicher Experimente.

[Bearbeiten] Softwaretechnische Realisierungen

• Arithmetische Zufallszahlengeneratoren basieren auf der Arithmetik. Irrationale Zahlen wie oder e können als Zufallszahlengeneratoren verwendet werden, indem man den gebrochenen Teil beliebiger Vielfache als Zufallszahlen nutzt. Nachteil des Verfahrens ist, dass sich irrationale Zahlen nur als Näherungswerte innerhalb der Rechengenauigkeit darstellen lassen.
• Rekursiver arithmetischer Zufallszahlengenerator: Diese Verfahren beruhen auf der Berechnung einer neuen Zufallszahl aus einer oder mehreren vorhergehenden Zahlen. Die neu erzeugte Zahl wird gespeichert und geht bei erneutem Aufruf des Zufallszahlengenerators in die Berechnung ein. Beim allerersten Aufruf des Zufallszahlengenerators muss ein willkürlich gewählter Startwert, die Saat (meist engl.: seed) verwendet werden.
  • Kongruenzgenerator
    • linearer Kongruenzgenerator
      • multiplikativer Kongruenzgenerator
      • gemischter linearer Kongruenzgenerator
    • Fibonacci-Generator
  • Inverser Kongruenzgenerator

[Bearbeiten] Hardwaretechnische Realisierungen

• Schieberegister mit Rückkopplung
  • lineares Schieberegister
  • nichtlineares Schieberegister

[Bearbeiten] Sonstige Zufallszahlengeneratoren

• Auszählreime in Kinderspielen stellen eine Art deterministischer Zufallszahlengeneratoren dar.
• Das Mischen bei einem Kartenspiel ist ein nicht-deterministischer Zufallszahlengenerator.

[Bearbeiten] Weblinks

• Webbasierter Zufallszahlengenerator/English
• Echte (physikalische) Zufallszahlengeneratoren und deren Theorie
• RQube - Komfortabler und kostenloser Generator für Quasizufallsequenzen [1]