Wie kann ich OSX's rand() den spektralen Test nicht bestehen?

Question

Für den Zweck einer Programmierklasse versuche ich, die Schwächen der Zufallszahlengeneratoren zu veranschaulichen, die normalerweise mit der Standard-C-Bibliothek kommen, speziell dem "schlechten Zufallsgenerator" rand(), der mit OSX kommt (siehe die Manpage).

Ich schrieb ein einfaches Programm, mein Verständnis der spektralen Test Test:

#include <stdio.h> 
#include <stdlib.h> 

int main() { 
    int i; 
    int prev = rand(); 
    int new; 

    for (i=0; i<100000; i++) { 
    new = rand(); 
    printf("%d %d\n", prev, new); 
    prev = new; 
    } 
    return 0; 
} 

Aber wenn ich die resultierende Scatterplot plotten, hier ist das, was ich bekommen:

würde ich habe etwas erwartet, das mehr Struktur zeigt, wie man findet on Wikipedia. Mache ich hier etwas falsch? Soll ich in mehr Dimensionen plotten?

UPDATE

pjs Vorschlag folgend ich auf dem Teil des Grundstücks vergrößert, wo die Zahlen kleiner als 1E7 sind, und hier ist das, was ich gefunden habe:

ich genau das finden, die gleichen Linien zeigten sich durch pjs. Sie scheinen vertikal zu sein, aber dies ist unmöglich, da dies bedeuten würde, dass einige Werte von rand() "übersehen" wurden. Wenn ich die Daten sort -n ist dies (eine Probe), was ich sehe:

571 9596797 
572 9613604 
575 9664025 
578 9714446 
580 9748060 
581 9764867 
584 9815288 
586 9848902 
587 9865709 
590 9916130 
592 9949744 
127774 13971 
127775 30778 
127780 114813 
127781 131620 
127782 148427 
127783 165234 
127785 198848 
127787 232462 
127788 249269 

Mit anderen Worten liegen die Punkte in Linien, die fast, aber nicht ganz, vertikal.

Answer 1

Lineare kongruente Generatoren leiden alle unter einem von George Marsaglia identifizierten Problem. "Marsaglias Theorem" besagt, dass k-Tupel (Vektoren der Länge k) auf eine begrenzte Anzahl von Hyperebenen fallen. Die Grenze ist m**(1/k), wobei k die Größe des Tupels und m die für den Modul des Generators verwendete Zahl ist. Wenn also der Modul (2**31 - 1) ist und Sie 3er-Sätze sehen, zeigt ein 3-D-Plot die Punkte, die nicht mehr als die Kubikwurzel von (2**31 - 1) oder ungefähr 1290 Ebenen fallen, wenn Sie von der richtigen Ausrichtung aus betrachtet werden.

Alle LCG's unterliegen dem Marsaglia-Theorem. Ein "guter" spielt an oder nahe der oberen Grenze, ein schlechter geht weit unter die obere Grenze. Das ist es, was der Spektraltest effektiv misst, und genau das haben Sie in Ihrem Wikipedia-Link gesehen - RANDU, die LCG aus der Hölle, produziert Drillinge, die in nur 15 Ebenen fallen.

Apples Generator für Kohlenstoffbibliotheken verwendet 16807 als Multiplikator und (2**31 - 1) als Modul. Wie LCG's gehen, ist es nicht wirklich so schlimm. Daher hat deine Handlung nicht die gleichen Extreme wie RANDU gezeigt. Wenn Sie jedoch gute Qualität wünschen, verwenden Sie keine LCG.

Nachtrag

Ich habe eine Milliarde Zahlen aus dem Apple-rand() Funktion, sondern nur gedruckt vor und kurbelte die, die gegangen, wo beide Werte des Paares waren weniger als 2 Millionen, das heißt, der Boden linke Ecke Ihres Grundstücks. Sicher genug, sie fallen auf Linien. Sie müssen nur wirklich hineinzoomen, um es wegen der Dichte der Linien zu sehen.

Der alte George war ein kluger Kerl!

Answer 2

die schlechte rand ist ein Kongruenzgenerator, das heißt, es ist von der Form der Annahme: Sie nur ein paar Begriffe nehmen und die Gleichungen für a und b lösen können

next = a * prev + b (mod RAND_MAX+1) 

. Danach sollten Sie in der Lage sein, eine Funktion der Ausgabe zu erzeugen, so dass die Struktur leicht erkennbar wird.