Il generatore di numeri casuali dà lo stesso primo risultato ma si comporta come previsto

Question

Utilizzando la classe casuale e un seme di tempo (NULL) la distribuzione uniforme fornisce sempre lo stesso primo risultato, anche con compilazioni diverse, ma dopo il primo output si comporta come ci si aspetterebbe un generatore di numeri pseudocasuali per comportarsi.

È questo per costruzione, o sto usando erroneamente?

MWE:

#include <ctime> 
#include <iostream> 
#include <random> 

using namespace std; 

default_random_engine gen(time(NULL)); 
uniform_int_distribution<int> dist(10,200); 

int main() 
{ 
    for(int i = 0; i < 5; i++) 
     cout<<dist(gen)<<endl; 

    return 0; 
} 

Le prime tre volte mi sono imbattuto questo programma ottengo le uscite di:

57 
134 
125 
136 
112 

Prima che il secondo tentativo ho deciso di cancellare riga vuota tra uniform_int_distribution e int main() solo per vedere se il seme era basato sul tempo di compilazione, come puoi vedere, non importava.

57 
84 
163 
42 
146 

Proprio in esecuzione di nuovo:

57 
73 
181 
160 
46 

Così via le mie corse Continuo a ricevere 57 prima, che ovviamente non è la fine del mondo, se voglio uscite differenti posso buttare via la prima uscita. Ma mette in discussione se questo è di progettazione (se sì, perché?) O se sto abusando del generatore in qualche modo (se sì, come?).

Answer 1

Non sono sicuro di cosa stia succedendo (ancora!), Ma è comunque possibile inizializzarlo in base al tempo come segue senza colpire il problema (preso in prestito da here).

#include <ctime> 
#include <iostream> 
#include <random> 
#include <chrono> 

using namespace std; 

unsigned seed1 = std::chrono::system_clock::now().time_since_epoch().count(); 

default_random_engine gen(seed1); //gen(time(NULL)); 
uniform_int_distribution<int> dist(10,200); 

int main() 
{ 
    for(int i = 0; i < 5; i++) 
     cout<<dist(gen)<<endl; 

    return 0; 
} 

È inoltre possibile utilizzare il dispositivo a caso, che non è determinstic (ruba cronometraggio informazioni dai vostri colpi chiave, movimenti del mouse e altre fonti per generare numeri imprevedibili). Questo è il seme più forte che puoi scegliere, ma l'orologio del computer è il modo migliore per andare se non hai bisogno di forti garanzie perché il computer può esaurire "casualità" se lo usi spesso (ci vogliono molti tratti chiave e mouse movimenti per generare un singolo numero veramente casuale).

std::random_device rd; 
default_random_engine gen(rd()); 

Esecuzione

cout<<time(NULL)<<endl; 
cout<<std::chrono::system_clock::now().time_since_epoch().count()<<endl; 
cout<<rd()<<endl; 

sulla mia macchina genera

1413844318 
1413844318131372773 
3523898368 

così la libreria chrono sta fornendo un numero significativamente più grande e più rapidamente il numero cambia (che è in nanosecondi) rispetto alla libreria ctime . Lo random_device sta producendo numeri non deterministici che si trovano su tutta la mappa. Quindi sembra che i semi che producono ctime possano essere troppo vicini tra loro in qualche modo e quindi mappare in parte allo stesso stato interno?

ho fatto un altro programma che assomiglia a questo:

#include <iostream> 
#include <random> 
using namespace std; 

int main(){ 
    int oldval   = -1; 
    unsigned int oldseed = -1; 

    cout<<"Seed\tValue\tSeed Difference"<<endl; 
    for(unsigned int seed=0;seed<time(NULL);seed++){ 
    default_random_engine gen(seed); 
    uniform_int_distribution<int> dist(10,200); 
    int val = dist(gen); 
    if(val!=oldval){ 
     cout<<seed<<"\t"<<val<<"\t"<<(seed-oldseed)<<endl; 
     oldval = val; 
     oldseed = seed; 
    } 
    } 
} 

Come si può vedere, questa stampa semplicemente il primo valore di uscita per ogni possibile seme casuale fino all'ora corrente con il seme e il numero di semi precedenti che avevano lo stesso valore.Un estratto della potenza è simile al seguente:

Seed Value Seed Difference 
0 10 1 
669 11 669 
1338 12 669 
2007 13 669 
2676 14 669 
3345 15 669 
4014 16 669 
4683 17 669 
5352 18 669 
6021 19 669 
6690 20 669 
7359 21 669 
8028 22 669 
8697 23 669 
9366 24 669 
10035 25 669 
10704 26 669 
11373 27 669 
12042 28 669 
12711 29 669 
13380 30 669 
14049 31 669 

Così, per ogni nuovo primo numero ci sono 669 semi che danno quel primo numero. Poiché il secondo e il terzo numero sono diversi, stiamo ancora generando stati interni unici. Penso che dovremmo capire molto di più su default_random_engine per capire cosa è speciale su 669 (che può essere scomposto in 3 e 223).

Dato questo, è chiaro il motivo per cui le librerie chrono e random_device funzionano meglio: i semi che generano sono sempre più di 669 a parte. Tieni presente che anche se il primo numero è lo stesso, ciò che conta in molti programmi è la sequenza di numeri generati da distinti.

Answer 2

il seme che si sta utilizzando potrebbe introdurre un bias, se l'utilizzo di un seme diverso produce gli stessi risultati, quindi il generatore stesso non viene scritto correttamente.

Vorrei suggerire test con semi diversi per trarre una conclusione.

Answer 3

Utilizzare std :: default_random_engine è come dire "Sorprendimi!" in un brutto ristorante. L'unica cosa che sai per certo è che il risultato sarà scarso - poiché i generatori forniti da <random> sono tutti carenti - ma non saprai nemmeno quali particolari difetti devi affrontare.

Il Mersenne Twister può essere una scelta decente se - e solo se - è correttamente seminato, e qui sta lo sfregamento. Idealmente, ogni bit del seme dovrebbe influenzare ogni bit dello stato del generatore risultante con uguale probabilità; come hai scoperto, non è il caso delle comuni implementazioni di std :: mersenne_twister_engine.

I Twister di Mersenne vengono normalmente inizializzati con l'output di un PRNG più semplice a sua volta seminato da qualsiasi entropia disponibile. Questo allunga efficacemente l'entropia del seme del PRNG più semplice sull'enorme stato del tornitore. I creatori dello standard hanno fornito con cura l'interfaccia seed_seq per questo scopo; tuttavia, sembra che la libreria non contenga adattatori per l'utilizzo di un generatore come sequenza di seed.

C'è anche la discrepanza tra due diverse concezioni di semina. Sul lato generatore, la funzione di semina dovrebbe prendere l'entropia che è stata passata e mapparla fedelmente sullo stato del generatore, assicurando che nessuna entropia venga persa nel processo. Dal lato utente, è "Prendi questi numeri e dammi sequenze molto diverse", dove "questi numeri" è l'uscita {1, 2, 3, ...} o clock().

In altre parole, l'entropia della semente viene offerta in una forma che non è adatta per inizializzare direttamente lo stato del generatore; piccole differenze di semi danno piccole differenze di stato. Questo è particolarmente problematico con enormi generatori ritardati come il Mersenne Twister o il ritardato Fibonacci che alimenta i generatori std :: ranluxXX.

Una funzione di missaggio bit, una funzione biiettiva in cui ogni bit dell'output dipende da ogni bit dell'input con uguale probabilità, può aiutare a rendere l'output di semi come 1, 2, 3 o clock() più utile per la semina . Il murmur hash mixer si avvicina a questo ideale, raggiungendo quasi perfetta diffusione (versione a 32 bit mostrato):

uint32_t murmur_mix32 (uint32_t x) 
{ 
    x ^= x >> 16; 
    x *= 0x85EBCA6B; 
    x ^= x >> 13; 
    x *= 0xC2B2AE35; 
    x ^= x >> 16; 

    return x; 
} 

la funzione biunivoca, quindi non perde alcuna entropia affatto. Questo significa che puoi usarlo per migliorare qualsiasi seme senza il rischio di peggiorare le cose.

Un'altra soluzione rapida, senza lo sforzo di fare un seed_seq, è di chiamare scarto() sul generatore con un parametro che dipende dal seme (mormorato). Tuttavia, l'effetto su enormi generatori come il Mersenne Twister è alquanto limitato, dal momento che il loro stato si evolve estremamente lentamente e hanno bisogno di centinaia di migliaia di iterazioni per il pieno recupero dagli stati deficitari.