In che modo le distribuzioni della classe C++ 11 <random> trasformano il generatore sottostante?

Question

Il seguente codice non sembra comportarsi in modo intuitivo:

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

int main() 
{ 

    mt19937 MyGenerator(40); 
    auto gauss = normal_distribution<double>(0,1); 
    auto linear = uniform_real_distribution<double>(0,1); 
    cout << gauss(MyGenerator) << endl; //line a 
    cout << linear(MyGenerator) << endl; //line b 
    cout << gauss(MyGenerator) << endl; 
} 

L'esecuzione di questo codice dà l'uscita

-0.816097 
0.705030 
0.303032. 

Se ora l'ordine delle linee A e B è scambiato, i cambiamenti di uscita per

0.644008 
0.338080 
-0.639501. 

È del tutto chiaro che i primi due numeri sono diversi ora, poiché sono prodotti da diverse distribuzioni. Tuttavia, perché il terzo numero è diverso? Nella mia intuizione, la distribuzione dovrebbe prendere un numero c = MyGenerator() che viene quindi mappato al numero casuale nell'intervallo specifico. Il generatore di numeri casuali indicherà il numero successivo nella sequenza di numeri dopo la chiamata di distribuzione. Quindi, l'esito della terza chiamata non dovrebbe essere lo stesso in entrambi i casi?

Un'altra osservazione: L'aggiunta di una quarta chiamata a una delle distribuzioni sembra infatti riprodurre gli stessi numeri.

Answer 1

L'implementazione di libstdC++ di normal_distribution utilizza lo Marsaglia polar method. La cosa interessante di questo metodo è che ogni passaggio utilizza due numeri casuali dall'URNG per generare due risultati.

Cioè, la prima chiamata alla distribuzione chiama l'URNG due volte (forse più volte, poiché utilizza il campionamento di reiezione, ma un numero pari di volte) e restituisce un risultato; la seguente chiamata alla distribuzione non chiamerà l'URNG ma restituirà il secondo risultato salvato.

Ecco un extract from the source code, scarsamente riformattato:

if (_M_saved_available) 
{ 
    _M_saved_available = false; 
    ret = _M_saved; 
} 
else 
{ 
    result_type x, y, r2; 
    do 
    { 
     x = result_type(2.0) * aurng() - 1.0; 
     y = result_type(2.0) * aurng() - 1.0; 
     r2 = x * x + y * y; 
    } 
    while (r2 > 1.0 || r2 == 0.0); 

    const result_type mult = std::sqrt(-2 * std::log(r2)/r2); 
    _M_saved = x * mult; 
    _M_saved_available = true; 
    ret = y * mult; 
} 

Answer 2

Non c'è alcun requisito che la distribuzione chiamare il generatore sottostante una volta per ogni valore. Alcune distribuzioni sono meglio calcolate combinando più valori casuali.

Ad esempio, nella realizzazione GNU, l'implemantation della distribuzione uniforme è

return (__aurng() * (__p.b() - __p.a())) + __p.a(); 

chiamando il generatore __aurng volta; mentre il nucleo della distribuzione normale è:

do 
{ 
    __x = result_type(2.0) * __aurng() - 1.0; 
    __y = result_type(2.0) * __aurng() - 1.0; 
    __r2 = __x * __x + __y * __y; 
} 
while (__r2 > 1.0 || __r2 == 0.0); 

chiamare almeno due volte.