Diskussion:Spektraltest

Wie berechnet man die Zahlen $\nu _{i}$ ? Wieso ist in den letzten Zeilen ("Horrorbespiel") die Wurzel aus 116 gleich 10 ${\sqrt {116}}=10$ ? -- 129.13.72.153 10:43, 20. Mai 2008 (CEST)

• Wie man die Zahlen berechnet kann man nicht mehr in einem Wikipedia-Artikel beschreiben. Suche Dir in einer Bibliothek (über Fernleihe) das Bucht von Knuth, hole tief Luft und lies die Mathematik. Wenn Du davor keine Angst hast - es sind Fouriertransformationen Frequenzräume Matrizen und Iterationsverfahren nötig. Wenn Du die programme brauchst, müsste man das über email machen.
• Man braucht nur die ganzzahligen Wurzeln 10*10 <= 116 < 11*11! --Brf 16:20, 20. Mai 2008 (CEST)

RANDU

Ich glaube, dass der erste Wert für RANDU nicht 23171, sondern 46338 lauten sollte -- zumindest ergibt es sowohl meine Rechnung von Hand als auch ein Programm (das allerdings denselben Algorithmus verwendet). Was mich in meiner Behauptung bestärkt, ist, dass die Werte des anderen (»typischen«) Zufallsgenerators exakt meinen berechneten entsprechen. (nicht signierter Beitrag von 87.155.72.228 (Diskussion) 17:46, 16. Jul 2010 (CEST))

Unverständlich

Die Zahlen sagen direkt etwas über die Genauigkeit der erhaltenen Zufallszahlen aus: Wenn man in einer Rechnung immer zwei Zufallszahlen benötigt, etwa weil man Zufallspunkte in der Ebene benötigt, kann man die Ergebnisse maximal mit einer Genauigkeit von 1 / ν2 = 1 / 67654 = 0.0000148 < 10 − 4 = 4 Dezimalstellen angeben. Wenn man drei pro Rechnung benötigt sind das 1 / ν3 = 1 / 1017 = 0.000938 < 10 − 3 = 3 Dezimalstellen. Bei vier pro Rechnung ergibt sich 1 / ν4 = 1 / 249 = 0.00402 < 10 − 2 = 2 Dezimalstellen.

Häh?? Ich brauche für ein Würfelspiel mit 2 Würfel zwei Zufallszahlen pro Wurf (Gleichverteilte Ganzzahlen 1 <= x <= 6). In welchem Zusammenhang stehen hier die Dezimalstellen? Dezimalstellen wovon? Was soll die Genauigkeit einer Zufallszahl sein? Für mich ergibt der Artikel auf weite Strecken keinen Sinn und ist insofern tatsächlich ein Fall für die QS. Leider schon seit einem dreiviertel Jahr. --Rat 20:31, 10. Mär. 2011 (CET)

Hier wird wohl im wesentlichen über Zufallszahlengeneratoren (ZZG) für eine stetig uniforme Verteilung geschrieben. In Computersoftware werden Zufallszahlen, die einer beliebigen Verteilung folgen, meist aus solchen Zufallszahlen generiert. Auch hinter dem Wurf mit zwei Würfeln steht ein ZZG der Zufallszahlen für eine stetig uniforme Verteilung erzeugt. D.h. die Qualität von solchen Zufallszahlengeneratoren ist wichtig. --Sigbert 20:53, 10. Mär. 2011 (CET)

Spektraltest für Java ?

Hallo, auch ich finde den Artikel über den Spektraltest sehr schwer verständlich. Aber es wird ja - zumindest auf der Diskusionsseite - explizit darauf hingewiesen, dass die dahintersteckende Mathemetik sehr kompliziert ist. Mit anderen Worten, mal schnell einen Spektraltest selbst zu programmieren, ist mehr oder weniger unmöglich. Es wird andererseits aber oft darauf hingewiesen, dass man den Spektraltest benutzen sollte, um die Güte eines Zufallsgzahlengenerators zu testen, bevor man diesen Zufallsgzahlengenerator wirklich verwendet. Leider steht aber den meisten Nutzern diese Möglichkeit nicht zur Verfügung, da der Spektraltest häufig nur in riesengroßen kostenpflichtigen Softwarepaketen angeboten wird, wo das Installieren und die Einarbeitung in das Softwarepaket oft schon Wochen dauert. Zudem sind diese Softwarepakete oft in einer Programmiersprache wie C/C entwickelt worden, die es auf einem Standard-Windowssystem meist gar nicht gibt. Ein Link zu einer kostenfreien Java-Softwarebibliothek, oder zu einer Web-Seite, welche einen Spektraltest online anbietet, denn man ohne großen Aufwand benutzen kann, wäre deshalb für viele sicherlich sehr hilfreich.

Als kostenfreie und in jeder Programmiersprache recht schnell zu programmierende einfache Spektraltestalternative mit absolut simpler Mathematik dahinter, kann ich vorerst nur die Bitvektorkorrelationsmatrix empfehlen, die mir schon seit Jahren immer wieder gute Dienste geliefert hat. Leider weiß ich heute nicht mehr, wo ich diese Methode vor vielen Jahren gefunden habe und ob der Name wirklich korrekt ist, jedenfalls ist sie nicht auf "meinem Mist" gewachsen. Aber sie ist einfach genug, um sie mit wenigen Worten zu erklären. --Aragorn321 (Diskussion) 14:34, 11. Jan. 2013 (CET)

Spektraltestalternative Bitvektorkorrelationsmatrix

Eine normierte Bitvektorkorrelationsmatrix $M$ dient zum einfachen Ermitteln von linearen Abhängigkeiten zwischen den einzelnen Bits zweier Bitvektoren $A$ und $B$ der Länge $n$. Sie ist deshalb stets quadratisch, hat also $n$ Zeilen und $n$ Spalten und für alle reellen Elemente $m_{i,j}\ (0<=i,j<n)$ dieser Matrix $M$ gilt $(-1.0<=m_{i,j}<= 1.0)$. Eine solche normierte Bitvektorkorrelationsmatrix macht natürlich nur dann einen Sinn, wenn sie eine Aussage über $(N>1)$ durchgeführte Vergleiche bzw. Tests von jeweils zwei verschiedenen Bitvektoren der Länge $n$ treffen kann.

Deswegen initialisiert man am Anfang einer Testreihe alle Elemente $m_{i,j}$ einer noch nicht normierten Bitvektorkorrelationsmatrix $M$ mit dem Wert 0 und addiert in jedem Test zu $m_{i,j}$ den Wert 1, wenn die zugehörigen Bits $a_{i}$ und $b_{j}$ gleich sind bzw. den Wert -1, wenn diese beiden Bits verschieden sind. Mehr Fälle gibt es bei zwei Bits ja nicht zu unterscheiden. Nach $N$ durchgeführten Vergleichen von jeweils zwei verschiedenen Bitvektoren gleicher Länge, enthält diese Matrix deshalb nur ganzzahlige Wert zwischen $-N$ und $N$. Um diese noch nicht normierte Bitvektorkorrelationsmatrix zu normieren, teilt man einfach jedes Matrixelement $m_{i,j}$ durch die Anzahl $N$ der durchgeführten Bitvektorvergleiche. Eine normierte Bitvektorkorrelationsmatrix ist also nicht mehr von der Anzahl $N$ der durchgeführten Versuche abhängig, mit anderen Worten: gleich große normierte Bitvektorkorrelationsmatritzen lassen sich stets problemlos miteinander vergleichen, egal wieviel Versuche man durchgeführt hat.

Hat nach $N=(100,1000,10000,100000,...)$ Bitvektorvergleichen ein Matrixelement $m_{i,j}$ einer normierten Bitvektorkorrelationsmatrix $M$ stets den Wert 1 oder -1, so sind die zugehörigen Bits $a_{i}$ und $b_{j}$ in allen getesteten Bitvektorpaaren eindeutig linear abhängig gewesen. Im Fall von 1 waren sie stets gleich, im Fall von -1 waren sie stets verschieden. Hat ein Matrixelement $m_{i,j}$ stets exakt den Wert 0, so existierte eine alternierende Abhängigkeit der beiden zugehörigen Bits $a_{i}$ und $b_{j}$, d.h. sie waren genauso oft gleich, wie sie verschieden waren, was sicherlich ebenfalls nix mit "echtem" Zufall zu tun haben kann. Sollte ein Matrixelement $m_{i,j}$ dagegen bei wachsender Anzahl $N$ von Versuchen tendenziell betragsmäßig immer kleiner werden, aber betragsmäßig stets größer als $1/N$ bleiben, so sind die zugehörigen Bits $a_{i}$ und $b_{j}$ höchstwahrscheinlich nicht linear abhängig voneiander. Gilt diese letzte Aussage für alle Matrixelemente $m_{i,j}$, so sind alle Bits beiden Bitvektoren höchstwahrscheinlich nicht linear abhängig voneinander, was bei einer brauchbaren Zufallszahlenfolge stets der Fall sein sollte. --Aragorn321 (Diskussion) 14:34, 11. Jan. 2013 (CET)

Beispiel für eine Bitvektorkorrelationsmatrix

Ich hoffe, dass diese - mathematisch wie programmiertechnisch gesehen - recht einfache und zugreifbare Methode von vielen Nutzern, inklusive mir selbst, wesentlich einfacher zu verstehen ist, als der wesentlich komplexere Spektraltest in unereichbarer Ferne. Zur besseren Anschaulichkeit sei hier noch ein konkretes Beispiel nachgereicht: Als Pseudozufallsgenerator dient hier der gemischte linerare Kongruenzgenerator $LCG64(a,b,m)$ mit einem Modul $m=2$⁶⁴, einem Fator $a=6364136223846793005$ und einem Offset $b=1442695040888963407$, so wie er in der Wikipedia unter http://en.wikipedia.org/wiki/Linear_congruential_generator zu finden ist. Die Zufallswerte werden also alle wie folgt berechnet: $x_{i 1}=(a*x_{i} b)\ mod\ m$. Der Startwert $x_{0}$ ist dabei beliebig. Ganz offensichtlich existiert eine lineare Abhängigkeit zwischen allen direkt aufeinanderfolgenden Werten, also $x_{i}$ mit $x_{i 1}$, was auch so in einer normierten Bitvektorkorrelationsmatrix zu erkennen sein müßte. Ich habe für dieses Beispiel nur mal die 4 niederwertigsten Bits der eigentlich jeweils 64 Bit langen Zufallswerte miteinander verglichen und dafür immer $N=1024*1024=2$²⁰ Bitvektorvergleiche durchgeführt.

-1,000000  0,000000  0,000000  0,000000 ...
 0,000000  0,000000  0,000000  0,000000 ...
 0,000000  0,000000  0,500000  0,000000 ...
 0,000000  0,000000  0,000000 -0,250000 ...
...

Aha, das niederwertigste Bit (also Bit 0) aller direkt aufeinanderfolgenden Zufallswerte ist stets verschieden und auch alle anderen Bitpaarungen scheinen absolut nicht zufällig zu sein. Vergleicht man nur jeden zweiten Bitvektor miteinander, also $x_{i}$ mit $x_{i 2}$, erhält man folgende normierte Bitvektorkorrelationsmatrix:

 1,000000  0,000000  0,000000  0,000000 ...
 0,000000 -1,000000  0,000000  0,000000 ...
 0,000000  0,000000  0,000000  0,000000 ...
 0,000000  0,000000  0,000000  0,000000 ...
...

Nun ist das niederwertigste Bit stets gleich und dafür ist das Bit 1 stets verschieden. Vergleicht man nur jeden vierten Bitvektor miteinander, also $x_{i}$ mit $x_{i 4}$, erhält man folgende normierte Bitvektorkorrelationsmatrix:

 1,000000  0,000000  0,000000  0,000000 ...
 0,000000  1,000000  0,000000  0,000000 ...
 0,000000  0,000000 -1,000000  0,000000 ...
 0,000000  0,000000  0,000000  0,000000 ...
...

Nun sind sogar die beiden niederwertigsten Bits stets gleich und dafür ist das Bit 2 stets verschieden. Dieses erkennbare Verhaltensmuster ließe sich nun beliebig fortsetzen. Da dieses katastrophale Verhaltensmuster allen gemischten linearen Kongruenzgeneratoren mit einer Zweierpotenz als Modul eigen ist, völlig egal, wie gut man die Parameter a und b optimiert hat (also bei allen praxisrelevanten linearen Kongruenzgeneratorn), rate ich dringend davon ab, irgendwelche lineare Kongruenzgeneratoren in ihrer originalen Form als Pseudozufallsgenerator zu verwenden.

Selbstverständlich hat man für dieses Problem aber schon längst eine Lösung gefunden, die auch auf der deutschen Web-Seite zu den linearen Kongruenzgeneratoren kurz erwähnt wird. Man verwendet z.B. einfach nur die K/2 höherwertigsten Bits der von linearen Kongruenzgeneratoren erzeugten Zufallswerte der Länge K, alle K/2 niederwertigen Bits ignoriert man. In unserem konkreten Fall bedeutet dies, dass man nur alle 64 Bit der generierten Zufallswerte um jeweils genau 32 Bits nach rechts schieben muss, mathematisch gesehen also nur durch 2³² dividieren braucht. Das heißt nur ein einziger einfacher Maschinenbefehl, der (auf allen 64 Bit-Computern) nur einen einzigen Takt benötigt, reicht vollkommen aus, um das oben beschriebene katastrophale Verhalten aller linearen Kongruenzgeneratoren mit einer Zweierpotenz als Modul auf einen Schlag zu beseitigen. --Aragorn321 (Diskussion) 14:34, 11. Jan. 2013 (CET)

Empfehlenswerte Nachbehandlung für alle lineare Kongruenzgeneratoren mit einer Zweierpotenz als Modul

Hier noch einmal das obige Beispiel mit dem nur leicht modifizierten linearen Kongruenzgenerator LCG64: $x_{i 1}=((a*x_{i} b)\ mod\ m)\ >>\ 32$:

-0,000042 -0,001318  0,001753  0,000690 ...
 0,001781 -0,000441  0,000162 -0,000420 ...
 0,000469  0,000109  0,000135 -0,000854 ...
-0,000166  0,001720  0,000954 -0,000109 ...
...

-0,000645 -0,000755  0,000620  0,001009 ...
-0,000486 -0,002371 -0,001862  0,000839 ...
-0,000551  0,000746  0,001083  0,000111 ...
-0,000509  0,000860 -0,001289 -0,000164 ...
...

 0,000328 -0,001472 -0,000755  0,001064 ...
 0,002010 -0,000217  0,000515  0,000828 ...
-0,000504 -0,001152 -0,000912  0,000164 ...
 0,001188 -0,000437 -0,001356 -0,000292 ...
...

Das sieht doch nun schon wesentlich zufälliger, also besser aus. Es gibt deshalb aus meiner Sicht absolut keinen Grund, gleich alle linearen Kongruenzgeneratoren, nur wegen ihres Problems mit den Hyperebenen generell zu verteufeln. Genau diese Nachbehandlungsmethode wird übrigens auch von dem in Java seit Version 1.1 integrierten Zufallsgenerator (und somit seit vielen vielen Jahren) verwendet, allerdings benutzt der dort verwendete LCG48 nur den wesentlich kleineren und somit "geheimdienstfreundlicheren" Modul 2⁴⁸. Wer in Java einen brauchbaren linearen Kongruenzgenerator mit längerer Periode haben will, muß sich also selber einen programmieren, was aber wie oben bewiesen, eigentlich ganz einfach ist. --Aragorn321 (Diskussion) 14:34, 11. Jan. 2013 (CET)