Zufallszahlengeneratoren


In Computerprogrammen werden "Zufallszahlen" nach bestimmten Algorithmen berechnet, d.h. es sind gar keine echten Zufallszahlen, sondern "Pseudozufallszahlen". Von den so bestimmten Pseudozufallszahlen verlangt man eine möglichst gute Annäherung an "echte" Zufallszahlen, z.B. sollten die einzelnen Ziffern mit gleicher relativer Häufigkeit auftreten, Wiederholungen von Ziffern sollten die gleiche relative Häufigkeit wie bei echten Zufallsziffern haben, usw.

Eingabe

Hier können extern erzeugte Zufallszahlen eingefügt oder von internen Zufallszahlengeneratoren erzeugt werden. Die Auswertung entnimmt man den folgenden Analysen.
Generator:

Rechenfehler-Typ 1
Rechenfehler-Typ 2
Linearer Kongruenz Algorithmus


Häufigkeitsanalyse

Die relative Häufigkeit der Ziffern 0 bis 9 wird angezeigt.
Ziffer Anzahl Anteil Erwartet
0 0.1
1 0.1
2 0.1
3 0.1
4 0.1
5 0.1
6 0.1
7 0.1
8 0.1
9 0.1

Pokertest

Beim Pokertest werden die Zufallszahlen in Fünfergruppen zerlegt und die relative Häufigkeit der vom Pokerspiel her bekannten Muster wird gezählt und mit dem Erwartungswert verglichen.
Art Anzahl Anteil Erwartet
Fünfer 0.0001
Vierer 0.0045
Full House 0.009
Dreier 0.072
Zwei Paare 0.108
Paar 0.504
Nichts 0.3024

Maximumtest

Beim Maximumtest wird wie beim Pokertest die Verteilung der Ziffern geprüft. Die Zufallszahlen werden in Dreiergruppen abc zerlegt und es wird gezählt, mit welcher relativen Häufigkeit die Ziffer b die größte Ziffer der Gruppe ist. Bei Gleichverteilung sollte die relative Häufigkeit 0,285 sein.
Anzahl abc Anzahl mit b maximal Anteil Erwartet
0.285

Anhang

Generator vom Rechenfehler-Typ

Er erzeugt Pseudozufallszahlen im Intervall (0;1). Zu einer (vorgegebenen) Anfangsvariable x wird z.B. 3,1415... addiert, die Zahl wird mit 8 potenziert und vom Ergebnis der Nachkommateil als neue Pseudozufallszahl ausgegeben. Hier werden also Fehler, die wegen der begrenzten Rechengenauigkeit auftreten, als Pseudozufallsziffern benützt. 

 Hier der Quellcode:
 
 function rnd()  /* Zufallszahl R in (0,1) */
    {   R=Math.pow(R+A,8);
        R-=Math.floor(R);
        return R;
    }

Im vorliegenden Fall gilt als Initialisierung:

var R=0.01*dat.getMinutes()+0.1*dat.getSeconds();

Hier können Sie eine andere Variable eingeben:

R=
A=

Anmerkung: Bei diesem Generator treten nach etlichen Wiederholungen sogar Unterschiede zwischen einzelnen JavaScript-Interpretern (Netscape - Explorer) auf, die den Algorithmus für krytographische Zwecke unbrauchbar machen kann: Verschlüsselung im Explorer kann nur wieder im Explorer entschlüsselt werden.

Rechenfehler-Typ 2

Eine andere Möglichkeit besteht z.B. in der Berechnung von irrationalen Logarithmen logba mit 1< a < b. Wegen der Rechenfehler werden die Nachkommastellen schnell pseudozufällig. Hier ein möglicher Quellcode (a=2, b=10):
var a=2,b=10;
function rnd()
    {  var r=0,i=2;
       while(i<1000000)  /* 1/i ist die letzte mögliche Dezimalstelle */
           {  a*=a;
              if(a>=b){a/=b;
                       r=1/i+r;
                      }
              i*=2;
           }
       return r;
    }
Hier können Sie andere Werte für a und b eingeben (Achtung: 1 < a < b !)
a=
b=

Linearer Kongruenz Algorithmus

Eine Startzahl S ("Seed") wird mit der Zahl A multipliziert, die Zahl B wird addiert. Das Ergebnis wird modulo M genommen, das ergibt die neue Zahl S. S/M ist eine Pseudozufallszahl in [0,1).

Hier der Quellcode des Generators.

function rnd()
        { S=(A*S+B)%M;
          return S/M;
        }
Im vorliegenden Fall gilt als Initialisierung:
var A=11113,B=1,M=524288,S=1123;
Hier können Sie eine andere Initialisierungsvariable eingeben:
A=
B=
M=
S=

Günstige bzw. ungünstige Wahlen:

Nach Knuth erhält man für M=2n die maximale Periodenlänge, wenn B ungerade und A mod 4 = 1 gilt. Da die Modulo-Arithmetik bei Integer-Typen "automatisch" durch Überlauf eingebaut ist, wird man meist M als Zweierpotenz wählen.
(In JavaScript hat man dabei jedoch Probleme: Es wird auf Gleitkomma-Arithmetik umgeschaltet. Im vorliegenden Fall n=19, A=11113, B=1 tritt noch keine Umschaltung ein)

Allgemeiner erhält man maximale Periodenlänge, wenn ggT(B;M)=1 und A-1 ein Vielfaches jedes Primfaktors von M und - falls M ein Vielfaches von 4 auch A-1 ein Vielfaches von 4 ist.

Literatur

A. Engel: Mathematisches Experimentieren mit dem PC, Klett 1991, ISBN 3-12-983360-9
A.Engel: Stochastik, Klett 1987, ISBN 3-12-983110-X
D.E. Knuth: The Art of Computer Programming, Vol.2, Addison-Wesley 1998, ISBN 0-201-89684-2
Fehler, Anregungen bitte an Thomas Gebhardt