C funzione random() e setstate non comportarsi come previsto

Question

Sono incerto il motivo per cui questi due blocchi di codice danno diverse uscite:

unsigned int seed1 = 0; 
char state1[256]; 
initstate(seed1, state1, 256); 
printf("%10ld\n", random()); 
printf("%10ld\n", random()); 
// Gives: 
// 1216130483 
// 1950449197 

vs.

unsigned int seed1 = 0; 
char state1[256]; 
initstate(seed1, state1, 256); 
printf("%10ld\n", random()); 
setstate(state1); 
printf("%10ld\n", random()); 
// Gives: 
// 1216130483 
// 625602885 

Perchè sono incomprensioni che cosa setstate() lo fa?

EDIT: È interessante notare che, un'occhiata a ciò che questo dà:

unsigned int seed1 = 0; 
char state1[256]; 
initstate(seed1, state1, 256); 
printf("%10ld\n", random()); 
setstate(state1); 
setstate(state1); 
printf("%10ld\n", random()); 
// Gives: 
// 1216130483 
// 1950449197 

Answer 1

Credo che la chiamata a initstate() non passa anche a quello stato, ma la chiamata alla setstate() fa, motivo per cui quest'ultima La chiamata random() restituisce un numero generato dal nuovo stato.

Answer 2

Entrambe le implementazioni sono corrette.

Setstate modifica semplicemente un puntatore statico nella routine per puntare al buffer.

All'iniziale è consentito eseguire la stessa operazione, ma è anche consentito modificare prima il contenuto del buffer. Se il PRNG è qualcosa come ARC4 o Spritz, il buffer deve essere una permutazione piuttosto che solo bit arbitrari. Se il PRNG è un generatore di feedback additivo non lineare, allora almeno uno dei bit bassi da qualche parte nello stato deve essere impostato o non funzionerà correttamente. E qualche lib hash ha il buffer di stato quindi non sarà facile dire quale tipo di PRNG è in uso solo dalle informazioni di seed + output. Non sono tenuti a; la lib può fare esattamente la stessa cosa per initstate e setstate se il generatore che sta usando è un LFSG o qualcosa che non richiede alcun formato particolare o ha bisogno di coerenza per il buffer. Ma se non si esegue initstate e il sistema operativo utilizza qualcosa che ha tali esigenze, la sequenza ripetibile potrebbe non essere così imprevedibile come si vorrebbe.

Answer 3

L'implementazione BSD di setstate carica le informazioni di stato ausiliario, per scopi di controllo degli errori, prima di memorizzarle nel vecchio buffer. Inoltre initstate e setstate sono le uniche funzioni che aggiornano queste informazioni. Ciò significa che quando viene utilizzato lo stesso buffer, loads stale state, stores the new data e updates the internal state with the former. Chiamando in questo modo setstate si alternerà il vecchio stato memorizzato e lo stato interno corrente, causando i risultati osservati quando chiamati due volte.

The comment for setstate dice che chiamarlo con il buffer corrente è OK, quindi questo è il comportamento previsto, o un bug decades old.

Nota che a causa l'ordine in cui sono fatte le cose, è OK per chiamare setstate() con lo stesso stato come lo stato attuale.

Answer 4

initstate() dice casuale quello di buffer da utilizzare per memorizzare le informazioni per la prossima di numeri casuali. È possibile ottenere risposte diverse nelle chiamate a random() poiché le informazioni nel buffer state1[256] sono state modificate.Guarda l'output del seguente codice:

#define LEN (32) 
void print_hex(char *b) 
{ 
    int i; 
    for(i=0; i < LEN; i++) printf("%02x ",((unsigned char *)b)[i]);  
    printf("\n"); 
} 

main() 
{ 
    char state1[256], state2[256], tmp[256]; 
    initstate(42, state2, LEN); 
    initstate(62, state1, LEN) ; 
    printf("buffer before random():\n"); 
    print_hex(state1) ; 
    printf("%10ld\n", random()); 
    printf("buffer after random():\n"); 
    print_hex(state1) ; 

    setstate(state2); // Now we are free to copy data from state1 
    printf("buffer after setstate():\n"); 
    print_hex(state1) ; 
    memcpy(tmp, state1, 256); 
    printf("copied to tmp\n"); 

    setstate(state1); // Go on with original sequence 
    printf("next random():\n") ; 
    printf("%10ld\n", random()); 
    printf("next random():\n") ; 
    printf("%10ld\n", random()); 

    setstate(state2) ; // Again, this allows us to play with data in state1 
    memcpy(state1, tmp, 256); 
    setstate(state1) ; 
    printf("back copy:\n"); 
    printf("random() after copy:\n") ; 
    printf("%10ld\n", random()); 
    printf("next random():\n") ; 
    printf("%10ld\n", random()); 
} 

Questo dà l'output:

buffer before random(): 
01 00 00 00 e7 22 1d 21 f1 62 9c 90 89 72 b5 89 35 2b 97 b5 76 8c ff a8 56 14 14 7b ba 19 d9 f7 
1801070350 
buffer after random(): 
01 00 00 00 e7 22 1d 21 f1 62 9c 90 89 72 b5 89 1c 4e b4 d6 76 8c ff a8 56 14 14 7b ba 19 d9 f7 
buffer after setstate(): 
06 00 00 00 e7 22 1d 21 f1 62 9c 90 89 72 b5 89 1c 4e b4 d6 76 8c ff a8 56 14 14 7b ba 19 d9 f7 
copied to tmp 
next random(): 
483260339 
next random(): 
    40158063 
back copy: 
random() after copy: 
483260339 
next random(): 
40158063 

Si può vedere che, dopo la prima chiamata a random() il contenuto del buffer di state1 modifiche. random() utilizza quell'area per memorizzare il suo stato. Questo stato viene copiato nel buffer tmp. Più tardi lo copiamo su state1 e otteniamo la stessa sequenza di numeri casuali. Si noti che prima di copiare in o da un buffer che si suppone debba essere utilizzato per numeri casuali è necessario comunicare allo random() di interrompere l'utilizzo di tale buffer utilizzando setstate() o initstate(). Il motivo è che quando viene chiamato il numero setstate(), il vecchio buffer viene modificato per consentirne il nuovo caricamento con setstate().

Quindi, per ottenere la stessa risposta nella domanda iniziale, è necessario utilizzare:

unsigned int seed1 = 42; 
char state1[256], tmp[256]; 
initstate(seed1, state1, 256); 
printf("%10ld\n", random()); 
initstate(0, tmp, 256); // <- notice this 
setstate(state1) ; 
printf("%10ld\n", random());