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 Abhängigkeit aufeinanderfolgender Ergebnisse ist unübersehbar. Der Generator hat auch eine zu kleine Periode sowie eine unvollständige und ungleichmäßige Verteilung.