generazione di numeri casuali in C++ utilizzando TR1/dev/random (resiliente a <1 secondo)

Question

Vorrei generare numeri casuali uniformi in C++ tra 0 e 1, in un modo che non utilizza il metodo standard rand() e srand(time(NULL)) . Il motivo è che se eseguo l'applicazione più volte nello stesso secondo del mio orologio, il seme sarà esattamente lo stesso e produrrà lo stesso risultato.

Non voglio fare affidamento su impulso o specifiche di OS/compilatore. x86 può essere assunto.

Sembra che un modo alternativo per farlo sia utilizzare TR1 (non ho C++ 11) e seminare con /dev/random in qualche modo?

In questo momento ho questo, ma usa ancora time(NULL) come un seme che non funziona bene all'interno 1 viene eseguito secondo:

#include <iostream> 
#include <tr1/random> 

int main() 
{ 
    std::tr1::mt19937 eng; 
    eng.seed(time(NULL)); 
    std::tr1::uniform_int<int> unif(1, RAND_MAX); 
    int u = unif(eng); 
    std::cout << (float)u/RAND_MAX << std::endl; 
} 

Answer 1

distacco su richiesta del PO:

Questo è ancora un po 'specifica per il compilatore, ma continuerà a funzionare su quasi tutti x86-targeting compilatori:

#ifdef _WIN32 

// Windows 
#define rdtsc __rdtsc 

#else 

// For everything else 
unsigned long long rdtsc(){ 
    unsigned int lo,hi; 
    __asm__ __volatile__ ("rdtsc" : "=a" (lo), "=d" (hi)); 
    return ((unsigned long long)hi << 32) | lo; 
} 

#endif 

int main() 
{ 
    std::tr1::mt19937 eng; 
    eng.seed(rdtsc()); // Seed with rdtsc. 
    std::tr1::uniform_int<int> unif(1, RAND_MAX); 
    int u = unif(eng); 
    std::cout << (float)u/RAND_MAX << std::endl; 
} 

L'idea è quella di seminare il tuo caso generatore di numeri con il contatore di cicli rdtsc.

Il motivo per cui questo funziona è perché il contatore di cicli rdtsc itera a circa (spesso la stessa) velocità della frequenza della CPU. Pertanto, le possibilità di due chiamate ad esso che restituiscono lo stesso valore sono estremamente ridotte, rendendo quindi un seme eccellente per un RNG.

Answer 2

Il tuo problema è legato al modo in cui si inizializzare il generatore di numeri casuali. Ovviamente la semina con il tempo (NULL) produrrà la stessa sequenza PRNG entro quel secondo seme. Questo è il modo più comune di seed rand, ma sfortunatamente è una cattiva pratica a causa di questo problema. Non solo, ho letto che può causare pregiudizi nei risultati.

noti che OGNI PRNG produce lo stesso risultato se seminato con gli stessi valori. Quindi il tuo problema non è legato al generatore, più alla semina.

ho fatto una domanda riguardo semina qui solo poche settimane fa ed è stato dato un link al seguente articolo, che si può anche trovare utili. Good Practice in (Pseudo) Random Number Generation for Bioinformatics Applications Vedere la sezione sulla semina o il riscaldamento del generatore.

rand() non è la migliore generatore di numeri casuali, ma è adatto in molti casi, purché esse siano correttamente seminato. Se vuoi qualcosa di meglio dove la sequenza di ripetizioni è molto grande, ci sono alcuni forniti in quel link. Oppure usa quelli basati su TR1. Personalmente, andrei con un codice basato su C++ 03 più portatile e eviterei TR1.

Considera anche Multiply with carry come un algoritmo PRNG alternativa.

Answer 3

TR1 in [tr.rand.device] specifica una classe random_device che genera valori non firmati da un'origine dipendente dall'implementazione. Così il seguente dovrebbe funzionare, anche se non ho compilato io stesso:

int main() { 
    std::tr1::random_device dev_random; 
    std::tr1::mt19937 eng(dev_random()); 
    ... 

In TR1, passando dev_random direttamente senza chiamare funziona e inizializza lo stato di ita più in modo casuale, ma in C++ 11 si deve avvolgere seme argomenti in un'altra classe.Poiché chiamare l'argomento funziona in entrambe le librerie, lo farei per la manutenibilità, a meno che non si abbiano esigenze più complesse.