Pseudozufallszahlen Tests
 
StartSeite | Neues | TestSeite | ForumSeite | Teilnehmer | Kategorien | Index | Hilfe | Einstellungen | Ändern

Ein interessantes Experiment für Anwender, die den eingebauten Pseudo-Zufallszahlengenerator ihrer Programmiersprache benutzen wollen, um unabhängige Zufallsgrößen zu simulieren:

Nehmen wir an, ein Pseudo-Zufallszahlengenerator kann ganze Zahlen zwischen 0 und einer Obergrenze größer als 200 liefern. Nun werden Paare (X, Y) von Pseudo-Zufallszahlen erzeugen. Immer dann, wenn die beiden aufeinanderfolgende Pseudozufallszahlen beide kleiner als 200 sind, wird der Punkt (X, Y) auf einer Fläche der Dimension 200x200 markiert.

Bei einem naiven linearen Verfahren zur Erzeugung von Zufallszahlen lassen sich die Hyperebenen, auf denen die aufeinanderfolgenden Pseudozufallszahlen liegen, so mit blossem Auge erkennen.

Der Test ist dann sinnvoll, wenn nicht dokumentiert ist, auf welche Weise die Pseudozufallszahlen erzeugt werden. Wenn schon in der Dokumentation steht, dass es ein additiver nichtlinearer Pseudozufallszahlengenerator ist, dann lohnt es sich nur für sehr misstrauische Anwender, auf diese Weise die Unkorreliertheit aufeinanderfolgender Pseudozufallszahlen zu prüfen.

Ein Bash-Skript zum Erzeugen von Testdaten könnte so aussehen

#!/bin/bash
while [ "$(wc -l < rand)" -lt 1000 ]
do
    RAND1=$RANDOM
    RAND2=$RANDOM
    [ $RAND1 -lt 200 ]  && [ $RAND2 -lt 200 ]  &&          echo $RAND1 $RAND2
done >rand

Dieses Skript läuft recht lange und erzeugte mit der 2.05.0(1)-release-Version der bash unter SuSE Linux 7.3 das folgende Ergebnis:

Auf diese Weise erzeugte Pseudozufallszahlen können ohne grosse Bedenken zur Simulation unabhängiger Ziehungen aus einer höherdimensionalen Gleichverteilung verwendet werden.

#!/bin/bash
while [ "$(wc -l < rand)" -lt 1000 ] ; do 
    RAND1=$(( $RANDOM / 60 ))
    RAND2=$(( $RANDOM / 60 ))
    [ $RAND1 -lt 200 ]          && [ $RAND2 -lt 200 ]          && echo $RAND1 $RAND2 
done > rand

läuft zwar deutlich kürzer, würde aber einen naiven Pseudozufallszahlengenerator nicht erkennen helfen, weil die möglicherweise vorhandenen Hyperebenen durch die Divison der Pseudozufallszahlen mit 60 so nahe zusammengeschoben würden, dass sie mit dem Auge nicht mehr zu erkennen wären.

Das Skript erzeugt mit der bash-Version 2.05a mit der glibc 2.2.5:

Dem Ersteller dieser Graphik fiel dabei besonders der Punkt an (0,0) und die freie Fläche bis (20,20) auf. Beides ist aber kein Hinweis auf das mit diesem Test nachzuweisende Problem mit einem Pseudozufallszahlengenerator und ließ sich in einem zweiten Durchlauf des Scripts auch nicht reproduzieren.

local n=0 rand1=00000 rand2=00000
> randf
while [ n -lt 1000 ]
do
   rand1=$RANDOM rand2=$RANDOM
   [ rand1 -lt 200 -a rand2 -lt 200 ] && {
      let ++n
      echo $rand1 $rand2
   }
done
><
Dies bsh-Script läuft etwa 600-fach schneller. Ist in ein paar Minuten fertig.
local n=0000 rand1=00000 rand2=00000
> Rand
while [ n -lt 1000 ]
do
   rand1=$RANDOM
   [ rand1 -lt 200 ] || continue
   rand2=$RANDOM
   [ rand2 -lt 200 ] || continue
   let ++n
   echo $rand1 $rand2
done
><
Dies bsh-Script läuft etwa 1200-fach schneller. Etwa 4 min auf PIII/700.

So nicht

Als Negativbeispiel hier ein linearer Kongruenzgenerator (der üblen Sorte):

int bad_random()
{
        static int random_state = 0;

        random_state += 137;
        random_state *= 7;
        random_state %= 199;

        return random_state;
}

Achtung, hier kann volatile notwendig sein, weil sonst ...

volatile verhindert, dass des Compiler auf die Bewertung von random_state verzichtet, wenn er aus der Datenflussanalyse weiss, welchen Wert random_state hat). Nachdem aber
 random_state = ((random_state + 137) * 7) % 199;
wirklich das ist, was hier bezweckt werden soll, würde es nicht stören, wenn der Compiler sein "Wissen" hier einsetzt.

Die ersten 1000 Zahlenpaare sehen so aus:

Die Abhängigkeit aufeinanderfolgender Ergebnisse ist unübersehbar. Der Generator hat auch eine zu kleine Periode sowie eine unvollständige und ungleichmäßige Verteilung.


KategorieAlgorithmus
StartSeite | Neues | TestSeite | ForumSeite | Teilnehmer | Kategorien | Index | Hilfe | Einstellungen | Ändern
Text dieser Seite ändern (zuletzt geändert: 5. Juni 2002 11:21 (diff))
Suchbegriff: gesucht wird
im Titel
im Text