Generazione di numeri casuali in C ++ 11, come generare, come funzionano?

Recentemente ho trovato un nuovo modo di generare numeri casuali in C ++ 11, ma non ho potuto digerire i documenti che ho letto su di esso (che cos’è quel motore, termine matematico come distribuzione, “dove tutti gli interi prodotti sono ugualmente probabili “).

Quindi qualcuno può spiegare cosa sono, cosa significano, come generare, come funzionano? ecc. (puoi chiamarlo tutto in una FAQ sulla generazione di numeri casuali).

La domanda è troppo generica per una risposta completa, ma lasciatemi scegliere un paio di punti interessanti:

Perché “altrettanto probabile”

Supponiamo di avere un semplice generatore di numeri casuali che genera i numeri 0, 1, …, 10 ciascuno con uguale probabilità (pensate a questo come al classico rand() ). Ora vuoi un numero casuale nell’intervallo 0, 1, 2, ciascuno con uguale probabilità. La tua reazione istintiva sarebbe prendere rand() % 3 . Ma aspetta, i restanti 0 e 1 si verificano più spesso del resto 2, quindi non è corretto!

Questo è il motivo per cui abbiamo bisogno di distribuzioni appropriate, che prendono una fonte di interi casuali uniformi e li trasformano nella nostra distribuzione desiderata, come Uniform[0,2] nell’esempio. Meglio lasciare questo ad una buona biblioteca!

motori

Quindi, al centro di ogni casualità c’è un buon generatore di numeri pseudo-casuali che genera una sequenza di numeri distribuiti uniformsmente su un certo intervallo e che idealmente hanno un periodo molto lungo. L’implementazione standard di rand() non è spesso la migliore, e quindi è bene avere una scelta. La congruenza lineare e il twister Mersenne sono due buone scelte (LG è spesso usato anche da rand() ); di nuovo, è bene lasciare che sia la biblioteca a gestirlo.

Come funziona

Facile: innanzitutto, impostare un motore e seminarlo. Il seme determina completamente l’intera sequenza di numeri “casuali”, quindi a) usa uno diverso (ad esempio tratto da /dev/urandom ) ogni volta, e b) memorizza il seme se desideri ricreare una sequenza di scelte casuali.

 #include  typedef std::mt19937 MyRNG; // the Mersenne Twister with a popular choice of parameters uint32_t seed_val; // populate somehow MyRNG rng; // eg keep one global instance (per thread) void initialize() { rng.seed(seed_val); } 

Ora possiamo creare distribuzioni:

 std::uniform_int_distribution uint_dist; // by default range [0, MAX] std::uniform_int_distribution uint_dist10(0,10); // range [0,10] std::normal_distribution normal_dist(mean, stddeviation); // N(mean, stddeviation) 

… E usa il motore per creare numeri casuali!

 while (true) { std::cout << uint_dist(rng) << " " << uint_dist10(rng) << " " << normal_dist(rng) << std::endl; } 

Concorrenza

Un altro motivo importante per preferire rispetto al tradizionale rand() è che ora è molto chiaro e ovvio come rendere la generazione di numeri casuali in modo sicuro: o fornire ciascun thread con il proprio motore thread-local, inserito in una discussione seed locale o sincronizzare l'accesso all'object motore.

Varie

  • Un interessante articolo su TR1 random su codeguru.
  • Wikipedia ha un buon sumrio (grazie, @Justin).
  • In linea di principio, ogni motore dovrebbe result_type un result_type , che è il tipo integrale corretto da utilizzare per il seme. Penso che una volta ho implementato un buggy che mi ha costretto a forzare il seed per std::mt19937 a uint32_t su x64, eventualmente questo dovrebbe essere corretto e si può dire MyRNG::result_type seed_val e quindi rendere il motore molto facilmente sostituibile.

Un generatore di numeri casuali è un’equazione che, dato un numero, ti darà un nuovo numero. In genere si fornisce il primo numero o viene estratto da qualcosa come l’ora del sistema.

Ogni volta che chiedi un nuovo numero usa il numero precedente per eseguire l’equazione.

Un generatore di numeri casuali non è considerato molto buono se ha la tendenza a produrre lo stesso numero più spesso di altri numeri. cioè se volevi un numero casuale tra uno e 5 e avevi questa distribuzione di numeri:

  • 1: 1%
  • 2: 80%
  • 3: 5%
  • 4: 5%
  • 5: 9%

2 è generato FAR più spesso di qualsiasi altro numero, quindi è più probabile che venga prodotto rispetto ad altri numeri. Se tutti i numeri fossero uguali, avresti una probabilità del 20% di ottenere ogni numero ogni volta. Per dirlo in un altro modo, la distribuzione di cui sopra è molto irregolare perché 2 è favorito. Una distribuzione con tutto il 20% sarebbe pari.

In genere, se si desidera un vero numero casuale, si estraggono dati da qualcosa come meteo o qualche altra fonte naturale piuttosto che un generatore di numeri casuali.