Modo consigliato per inizializzare srand?

Ho bisogno di un modo ‘buono’ per inizializzare il generatore di numeri pseudo-casuali in C ++. Ho trovato un articolo che afferma:

Al fine di generare numeri casuali, srand viene in genere inizializzato su un valore distintivo, come quelli relativi al tempo di esecuzione. Ad esempio, il valore restituito dal tempo della funzione (dichiarato nell’intestazione ctime) è diverso ogni secondo, che è abbastanza distintivo per la maggior parte delle esigenze di randoming.

Unixtime non è abbastanza distintivo per la mia applicazione. Qual è un modo migliore per inizializzare questo? Punti bonus se è portatile, ma il codice verrà eseguito principalmente su host Linux.

Stavo pensando di fare una matematica pid / unixtime per ottenere un int, o possibilmente leggere dati da /dev/urandom .

Grazie!

    MODIFICARE

    Sì, in realtà sto avviando la mia applicazione più volte al secondo e ho incontrato collisioni.

    La migliore risposta è usare il numero casuale di Boost. Oppure se hai accesso a C ++ 11 usa l’intestazione .

    Ma se stiamo parlando di rand() e srand()
    Il modo migliore è solo usare time() :

     int main() { srand(time(NULL)); ... } 

    Assicurati di farlo all’inizio del tuo programma, e non ogni volta che chiami rand() !

    Ogni volta che si avvia, time () restituirà un valore univoco (a meno che non si avvii l’applicazione più volte al secondo). Nei sistemi a 32 bit, si ripeterà solo ogni 60 anni circa.

    So che non pensi che il tempo sia abbastanza unico, ma lo trovo difficile da credere. Ma sono stato conosciuto per essere sbagliato.

    Se si stanno avviando contemporaneamente molte copie della propria applicazione, è ansible utilizzare un timer con una risoluzione più precisa. Ma poi corri il rischio di un periodo di tempo più breve prima che il valore si ripeta.

    OK, quindi se pensi davvero di iniziare più applicazioni al secondo.
    Quindi utilizzare una grana più fine sul timer.

      int main() { struct timeval time; gettimeofday(&time,NULL); // microsecond has 1 000 000 // Assuming you did not need quite that accuracy // Also do not assume the system clock has that accuracy. srand((time.tv_sec * 1000) + (time.tv_usec / 1000)); // The trouble here is that the seed will repeat every // 24 days or so. // If you use 100 (rather than 1000) the seed repeats every 248 days. // Do not make the MISTAKE of using just the tv_usec // This will mean your seed repeats every second. } 

    Questo è quello che ho usato per piccoli programmi a riga di comando che possono essere eseguiti frequentemente (più volte al secondo):

     unsigned long seed = mix(clock(), time(NULL), getpid()); 

    Dove il mix è:

     // http://www.concentric.net/~Ttwang/tech/inthash.htm unsigned long mix(unsigned long a, unsigned long b, unsigned long c) { a=ab; a=ac; a=a^(c >> 13); b=bc; b=ba; b=b^(a << 8); c=ca; c=cb; c=c^(b >> 13); a=ab; a=ac; a=a^(c >> 12); b=bc; b=ba; b=b^(a << 16); c=ca; c=cb; c=c^(b >> 5); a=ab; a=ac; a=a^(c >> 3); b=bc; b=ba; b=b^(a << 10); c=ca; c=cb; c=c^(b >> 15); return c; } 

    se hai bisogno di un generatore di numeri casuali migliore, non usare libc rand. Usate invece qualcosa come /dev/random o /dev/urandom direttamente (leggete in un int direttamente da esso o qualcosa del genere).

    L’unico vero vantaggio di libc rand è che dato un seed, è prevedibile che aiuta con il debug.

    Su Windows:

     srand(GetTickCount()); 

    fornisce un seed migliore di time() dal suo in millisecondi.

    Il modo migliore è usare un altro generatore di numeri pseudocasuali. Mersenne twister (e Wichmann-Hill) è la mia raccomandazione.

    http://en.wikipedia.org/wiki/Mersenne_twister

    ti suggerisco di vedere il file unix_random.c nel codice mozilla. (suppongo che sia mozilla / security / freebl / …) dovrebbe essere nella libreria freebl.

    lì usa le informazioni sulla chiamata di sistema (come pwd, netstat ….) per generare rumore per il numero casuale, è scritto per supportare la maggior parte delle piattaforms (che possono ottenere punti bonus: D).

    C ++ 11 random_device

    Se hai bisogno di una qualità ragionevole, non dovresti usare rand () in primo luogo; dovresti usare la libreria . Fornisce molte grandi funzionalità come una varietà di motori per diversi compromessi tra qualità / dimensioni / prestazioni, re-entrancy e distribuzioni predefinite in modo da non finire per sbagliare. Può anche fornire un facile accesso a dati casuali non deterministici, (ad es. / Dev / random), a seconda dell’implementazione.

     #include  #include  int main() { std::random_device r; std::seed_seq seed{r(), r(), r(), r(), r(), r(), r(), r()}; std::mt19937 eng(seed); std::uniform_int_distribution<> dist{1,100}; for (int i=0; i<50; ++i) std::cout << dist(eng) << '\n'; } 

    eng è una fonte di casualità, qui un'implementazione incorporata di mersenne twister. Lo seminiamo usando random_device, che in qualsiasi implementazione decente sarà un RNG non deterministico e seed_seq per combinare più di 32 bit di dati casuali. Ad esempio in libc ++ random_device accede / dev / urandom di default (sebbene tu possa dargli un altro file per accedere invece).

    Quindi creiamo una distribuzione tale che, data una fonte di casualità, le ripetute chiamate alla distribuzione produrranno una distribuzione uniforms di valori da 1 a 100. Quindi procediamo ad usare ripetutamente la distribuzione e a stampare i risultati.

    La vera domanda che devi porsi è quale sia la qualità di casualità di cui hai bisogno.

    libc random è un LCG

    La qualità della casualità sarà bassa qualunque sia l’input che fornisci con.

    Se devi semplicemente assicurarti che le diverse istanze abbiano diverse inizializzazioni, puoi unire id di processo (getpid), id di thread e un timer. Mescolare i risultati con xor. L’entropia dovrebbe essere sufficiente per la maggior parte delle applicazioni.

    Esempio :

     struct timeb tp; ftime(&tp); srand(static_cast(getpid()) ^ static_cast(pthread_self()) ^ static_cast(tp.millitm)); 

    Per una migliore qualità casuale, usa / dev / urandom. Puoi rendere portatile il codice precedente usando boost :: thread e boost :: date_time.

    La versione c++11 del più votato post di Jonathan Wright:

     #include  #include  #include  ... const auto time_seed = static_cast(std::time(0)); const auto clock_seed = static_cast(std::clock()); const size_t pid_seed = std::hash()(std::this_thread::get_id()); std::seed_seq seed_value { time_seed, clock_seed, pid_seed }; ... // Eg seeding an engine with the above seed. std::mt19937 gen; gen.seed(seed_value); 
     #include  #include  main() { struct timeval tv; gettimeofday(&tv,NULL); printf("%d\n", tv.tv_usec); return 0; } 

    tv.tv_usec è in microsecondi. Questo dovrebbe essere seme accettabile.

    Supponiamo di avere una funzione con una firma come:

     int foo(char *p); 

    Un’eccellente fonte di entropia per un seme casuale è un hash di quanto segue:

    • Il risultato completo di clock_gettime (secondi e nanosecondi) senza buttare via i bit bassi: sono i più preziosi.
    • Il valore di p , lanciato su uintptr_t .
    • L’indirizzo di p , lanciato su uintptr_t .

    Almeno il terzo, e forse anche il secondo, derivano entropia dall’ASLR del sistema, se disponibile (l’indirizzo stack iniziale, e quindi l’indirizzo stack corrente, è in qualche modo casuale).

    srand anche l’utilizzo di rand / srand interamente, sia per non toccare lo stato globale, sia per avere più controllo sul PRNG che viene utilizzato. Ma la procedura sopra descritta è un buon modo (e abbastanza portabile) per ottenere una discreta entropia senza molto lavoro, indipendentemente da quale PRNG usi.

    Per chi usa Visual Studio, ecco un altro modo:

     #include "stdafx.h" #include  #include  const __int64 DELTA_EPOCH_IN_MICROSECS= 11644473600000000; struct timezone2 { __int32 tz_minuteswest; /* minutes W of Greenwich */ bool tz_dsttime; /* type of dst correction */ }; struct timeval2 { __int32 tv_sec; /* seconds */ __int32 tv_usec; /* microseconds */ }; int gettimeofday(struct timeval2 *tv/*in*/, struct timezone2 *tz/*in*/) { FILETIME ft; __int64 tmpres = 0; TIME_ZONE_INFORMATION tz_winapi; int rez = 0; ZeroMemory(&ft, sizeof(ft)); ZeroMemory(&tz_winapi, sizeof(tz_winapi)); GetSystemTimeAsFileTime(&ft); tmpres = ft.dwHighDateTime; tmpres <<= 32; tmpres |= ft.dwLowDateTime; /*converting file time to unix epoch*/ tmpres /= 10; /*convert into microseconds*/ tmpres -= DELTA_EPOCH_IN_MICROSECS; tv->tv_sec = (__int32)(tmpres * 0.000001); tv->tv_usec = (tmpres % 1000000); //_tzset(),don't work properly, so we use GetTimeZoneInformation rez = GetTimeZoneInformation(&tz_winapi); tz->tz_dsttime = (rez == 2) ? true : false; tz->tz_minuteswest = tz_winapi.Bias + ((rez == 2) ? tz_winapi.DaylightBias : 0); return 0; } int main(int argc, char** argv) { struct timeval2 tv; struct timezone2 tz; ZeroMemory(&tv, sizeof(tv)); ZeroMemory(&tz, sizeof(tz)); gettimeofday(&tv, &tz); unsigned long seed = tv.tv_sec ^ (tv.tv_usec << 12); srand(seed); } 

    Forse un po 'eccessivo, ma funziona bene per intervalli veloci. funzione gettimeofday trovata qui .

    Modifica: dopo ulteriori indagini rand_s potrebbe essere una buona alternativa per Visual Studio, non è solo un rand sicuro (), è completamente diverso e non utilizza il seme di srand. Avevo presunto che fosse quasi identico a Rand solo "più sicuro".

    Per usare rand_s non dimenticare di #define _CRT_RAND_S prima che stdlib.h sia incluso.

    Finché il tuo programma funziona solo su Linux (e il tuo programma è un eseguibile ELF), sei sicuro che il kernel fornisce al tuo processo un seme casuale unico nel vettore aux ELF. Il kernel ti dà 16 byte casuali, diversi per ogni processo, che puoi ottenere con getauxval(AT_RANDOM) . Per usare questi per srand , usa solo un int di loro, in quanto tale:

     #include  void initrand(void) { unsigned int *seed; seed = (unsigned int *)getauxval(AT_RANDOM); srand(*seed); } 

    Potrebbe essere ansible che ciò si traduca anche in altri sistemi basati su ELF. Non sono sicuro di quali valori ausiliari siano implementati su sistemi diversi da Linux.

    Includi l’intestazione nella parte superiore del tuo programma e scrivi:

     srand(time(NULL)); 

    Nel tuo programma prima di dichiarare il tuo numero casuale. Ecco un esempio di un programma che stampa un numero casuale compreso tra uno e dieci:

     #include  #include  using namespace std; int main() { //Initialize srand srand(time(NULL)); //Create random number int n = rand() % 10 + 1; //Print the number cout << n << endl; //End the line //The main function is an int, so it must return a value return 0; }