W jaki sposób mogę sprawić, że OS RandX() nie przejdzie testu spektralnego?

Question

Dla celów klasy programistycznej próbuję zilustrować słabości generatorów liczb losowych, które zwykle pochodzą ze standardowej biblioteki C, w szczególności "zły generator losowy" rand(), który pochodzi z OSX (quoth the manpage).

Napisałem prosty program do testowania moje rozumienie widmowej testu:

#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; 
} 

Ale kiedy wykreślić wynikowy rozrzutu, oto co mam:

bym spodziewałem się czegoś o większej strukturze, na przykład tego, co znajduje się on Wikipedia. Czy robię coś złego tutaj? Czy powinienem kreślić w większej ilości wymiarów?

UPDATE

Po sugestii PJS koszulka I zbliżeniu na części działki, gdzie liczby są mniejsze niż 1E7, i oto co znalazłem:

znajdę dokładnie te same linie pokazane przez pjs. Wydają się być pionowe, ale jest to niemożliwe, ponieważ oznaczałoby to, że niektóre wartości zostały "pominięte" przez rand(). Kiedy sort -n dane jest (próbka), co widzę:

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 

Innymi słowy, punkty leżą na liniach, które są prawie, ale nie całkiem pionowe.

Answer 1

Liniowe generatory kongruencji wszystkie cierpią na problem zidentyfikowany przez George Marsaglia. "Twierdzenie Marsaglia" mówi, że k-krotki (wektory o długości k) spadną na ograniczoną liczbę hiperpłaszczyzn. Powiązanie to m**(1/k), gdzie k jest rozmiarem krotki, a m jest liczbą używaną dla modułu generatora. Tak więc, jeżeli moduł wynosi (2**31 - 1) i oglądasz zbiory 3, wykres 3-ci pokaże punkty spadające na nie więcej niż pierwiastek kostki z (2**31 - 1), lub około 1290 płaszczyzn, patrząc od prawej orientacji.

Wszystkie LCG podlegają Twierdzeniu Marsaglii. "Dobry" wykonuje się przy górnej granicy lub w jej pobliżu, a zły źle daleko od górnej granicy. To właśnie test spektralny skutecznie mierzy, i to właśnie widzieliście w linku do Wikipedii - RANDU, LCG z piekła rodem, produkuje trojaczki, które mieszczą się w zaledwie 15 płaszczyznach.

Generator biblioteki węglowej Apple używa 16807 jako mnożnika i (2**31 - 1) jako jego modułu. Jak idzie LCG, wcale nie jest tak źle. Dlatego twoja fabuła nie wykazała takich samych skrajności, jak RANDU. Jednak jeśli chcesz przyzwoitą jakość losowe numery nie używać LCG.

Uzupełnienie

Poszedłem do przodu i łukowaty miliard numery z funkcji Jabłko rand(), ale tylko te, gdzie drukowane obie wartości pary były mniej niż 2 miliony, czyli dolna lewy róg twojej działki. Oczywiście, padają na linie. Musisz tylko powiększyć, aby to zobaczyć z powodu gęstości linii.

Stary George był sprytnym facetem!

Answer 2

Zakładając złe rand jest przystający generator liniowy, to znaczy, że to postać:

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

można po prostu wziąć kilka terminów i rozwiązywać równania a i b. Po tym, powinieneś być w stanie wygenerować funkcję wyjścia tak, że struktura staje się łatwo widoczna.