Come posso rendere OSX's rand() fallire il test dello spettro?

Question

Per gli scopi di una classe di programmazione sto cercando di illustrare i punti deboli dei generatori di numeri casuali che di solito vengono con la libreria C standard, in particolare il "generatore casuale errato" rand() fornito con OSX (quoth la manpage).

ho scritto un semplice programma per testare la mia comprensione del test spettrale:

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

Ma quando ho tracciare il grafico a dispersione risultante, ecco cosa ottengo:

lo farei mi aspettavo qualcosa che mostra più struttura, come quello che si trova on Wikipedia. Sto facendo qualcosa di sbagliato qui? Devo tracciare più dimensioni?

UPDATE

Seguendo il suggerimento di pigiama ho ingrandito da parte della trama dove i numeri sono più piccoli di 1E7, e qui è quello che ho trovato:

trovo esattamente le stesse linee mostrate dai pjs. Sembrano verticali, ma questo è impossibile in quanto implicherebbe che alcuni valori venissero "persi" da rand(). Quando sono sort -n i dati è (un campione di) ciò che vedo:

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 

In altre parole, i punti si trovano in linee che sono quasi, ma non del tutto, verticale.

Answer 1

I generatori a congruenza lineare soffrono tutti di un problema identificato da George Marsaglia. Il "Teorema di Marsaglia" afferma che le k-tuple (vettori di lunghezza k) cadranno su un numero limitato di iperpiani. Il limite è m**(1/k), dove k è la dimensione della tupla e m è il numero utilizzato per il modulo del generatore. Quindi, se il modulo è (2**31 - 1) e stai guardando insiemi di 3, un grafico a 3-d mostrerà i punti che cadono su nient'altro che la radice cubica di (2**31 - 1), o circa 1290 piani, se visualizzati dall'orientamento corretto.

Tutti gli LCG sono soggetti al Teorema di Marsaglia. Un "buono" si esibisce in corrispondenza o in prossimità del limite superiore, uno cattivo cade ben al di sotto del limite superiore. Questo è ciò che il test spettrale sta effettivamente misurando, ed è quello che stavi vedendo nel tuo link Wikipedia: RANDU, il LCG dell'inferno, produce terzine che cadono in soli 15 piani.

Il generatore di librerie di carbone di Apple utilizza 16807 come moltiplicatore e (2**31 - 1) come modulo. Come va LCG, non è poi così male. Quindi la tua trama non ha mostrato gli stessi estremi di RANDU. Tuttavia, se si desidera che i numeri casuali di qualità decente non utilizzino un LCG.

Addendum

Sono andato avanti ea gomito con un miliardo di numeri dalla funzione di Apple rand(), ma solo stampate quelli in cui entrambi i valori della coppia erano meno di 2 milioni di euro, vale a dire, il fondo angolo sinistro della trama. Abbastanza sicuro, cadono sulle linee. Hai solo bisogno di zoomare per vederlo a causa della densità delle linee.

Il vecchio George era un tipo intelligente!

Answer 2

Supponendo che il cattivo rand è un generatore lineare congruenziale, vale a dire che è della forma:

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

si può semplicemente prendere un paio di termini e risolvere le equazioni per a e b. Dopodiché, dovresti essere in grado di generare una funzione dell'output in modo tale che la struttura diventi immediatamente evidente.