12
Iun
2008

TR1 aduce un nou header bibliotecii standard, numit <random< care defineste cateva generatoare de numere. Pana la TR1 singurul mod de a genera numere aleatoare in C++ era folosirea functiei rand(). Aceasta, desi trivial de folosit si buna pentru majoritatea aplicatiilor nu e suficient de performanta pentru unele categorii de aplicatii. In acest caz dezvoltatorii apelau la alte implementari cu ar fi Marsenne Twister. TR1 aduce in C++ cateva astfel de generatoare, inclusiv twisterul Marsenne.

Din pacate documentatia pentru aceste generatoare este destul de simplista, iar exemplele in MSDN lipsesc cu desavarsire. Voi incerca in acest articol sa clarific modul de folosire al acestor generatoare.

Ce este un generator?

Un generator de numere aleatoare, contrar poate unei prime impresii, nu genereaza numere aleatoare ci "pseudo" aleatoare, numere care doar dau impresia ca sunt aleatoare. Generarea de numere inseamna executia unui algoritm, fiecare nou numar, depinzand intr-un fel sau altul de ultimul generat. Din aceasta cauza, orice astfel de algoritm are nevoia de un numar initial, numit "seed". Un algoritm care e initializat cu acelasi seed va genera aceiasi secventa de numere. Acesta este un aspect important, intrucat in practica se uita adesea sa se initializeze generatorul. Fiind un algoritm matematic bine determinat, si numerele generate sunt deterministe. Doar un generator hardware poate produce numere cu adevarat aleatoare.

Inainte de TR1

Asa cum spuneam anterior, pana la TR1 singura modalitate "standard" de a genera numere aleatoare, era folosind functia rand(). Exemplul de mai jos exemplifica folosirea ei pentru a genera numere in intervalul [0, 10).

int main()
{
   srand((unsigned int)time(NULL));
   for(int i = 0; i < 10; ++i)
   {
      std::cout << rand()%10 << " ";
   }
   std::cout << std::endl;

   return 0;
}

Dupa cum se observa prima data am initializat generatorul cu o valoare initiala, care este valoarea returnata de functia time(); cu alte cuvinte, numarul de secunde scurse de la 1 Ianuarie 1970. In lipsa acestei initializari, toate secventele generate vor fi identice.

Atentie, in cazul acestui mod de initializare, daca se fac doua apeluri la srand() in mai putin de 1 secunda, atunci algoritmul va fi initializat cu aceiasi valoarea, si secventele generate for fi identice.

Noutatile din TR1

TR1 aduce nou trei categorii de entitati: generatoare, motoare (engine) si distributii. Un generator este un obiect care produce numere pseudo-aleatoare. Un generator care produce numere uniform distribuite intr-un interval se numeste (motor). Motoarele si distributiile se pot combina pentru generarea de numere in doua moduri:

  • pasand un motor operatorului () al unei distributii, sau
  • folosind clasa variate_generator care combina un generator cu o distributie.

Motoare

Un motor e practic o sursa de numere uniform distribuite intre doua limite. Toate motoarele au urmatoarele functii:

  • min(), returneaza valoarea minima ce poate fi returnata de operatorul () al motorului;
  • max(), returneaza valoarea maxima ce poate fi returnata de operatorul () al motorului;
  • operator(), returneaza valoari (cate una la fiecare apel) uniform distribuite in intervalul min() si max();
  • seed(), initializeaza motorul cu valoarea de start; random_device nu ofera aceasta functie.

Motoarele sunt de doua feluri: simple si compuse.

Motoare simple:

  • liniar_congruential: reprezinta un generator liniar congruent, care genereaza numere dupa formula:
    x(i) = (A * x(i-1) + C) mod M
    
  • marsenne_twister: reprezinta o implementarea a twisterului Marsenne. Acest twister pastreaza o valoare pe W * (N-1) * R biti; se extrag W biti si cand toti biti au fost folositi valoarea este alterata prin amestecare si shiftare de biti.
  • subtract_with_carry: genereaza numere folosind urmatoarea formula:
    x(i) = (x(i - R) - x(i - S) - cy(i - 1)) mod M
    
    unde
    cy(i) = x(i - S) - x(i - R) - cy(i - 1) < 0 ? 1 : 0
    
  • subtract_with_carry_01: genereaza numere folosing urmatoarea formula:
    x(i) = (x(i - R) - x(i - S) - cy(i - 1)) mod 1
    
    unde
    cy(i) = if x(i - S) - x(i - R) - cy(i - 1) < 0 ? 2-W : 0
    
  • random_device: genereaza numere aleatoare folosind un dispozitiv extern.

Motoare compuse:

  • xor_combine: genereaza valori folosing doua motoare; valorile generate de acestea sunt shiftate in modul urmator:
    x(i) = (eng1(i) << S1) ^ (eng2(i) << S2)
    
  • discard_block: foloseste un alt generator pentru a genera numere, din care elimina o parte. Motorul se parametrizeaza cu un alt generator, dimensiunea secventei de numere considerate (P) si dimensiunea folosita din aceasta secventa (R). Generatorul returneaza cate un nou numar la primele R apeluri. Apoi, genereaza inca P-R numere care sunt ignorate, si procesul se repeta.

Pe langa acestea exista cateva typedef-uri dupa aceste motoare:

  • minstd_rand0: generator liniar congruent
    typedef linear_congruential<unsigned long, 16807, 0, 2147483647>
    	minstd_rand0;
    
  • minstd_rand: generator liniar congruent
    typedef linear_congruential<unsigned long, 48271, 0, 2147483647>
    	minstd_rand;
    
  • mt19937: generator marsenne
    typedef mersenne_twister<unsigned long, 32, 624, 397, 31, 0x9908b0df,
    	11, 7, 0x9d2c5680, 15, 0xefc60000, 18> mt19937;
    
  • ranlux_base_01: generator de scadere cu transport
  • ranlux3 si ranlux4: generator discard bloc bazat pe scadere cu transport
    typedef subtract_with_carry<unsigned long, 1 << 24, 10, 24> _Ranbase;
    typedef discard_block<_Ranbase, 223, 24> ranlux3;
    typedef discard_block<_Ranbase, 389, 24> ranlux4;
    
  • ranlux3_01 si ranlux4_01: generator discard bloc bazat pe scadere cu transport
    typedef subtract_with_carry_01<float, 24, 10, 24> _Ranbase_01;
    typedef discard_block<_Ranbase_01, 223, 24> ranlux3_01;
    typedef discard_block<_Ranbase_01, 389, 24> ranlux4_01;
    
  • ranlux_64_01: generator de scadere cu transport
    typedef subtract_with_carry_01<double, 48, 5, 12> ranlux64_base_01;
    

Distributii

In TR1, o distributie este o clasa care transforma un flux de numere aleatoare uniform distribuite (obtinute de la un motor), intr-un flux de numere aleatoare, cu o distributie particulara. Cu alte cuvinte, numerele pseudo-aleatoare generate de un motor sunt intotdeauna uniform distribuite. Pentru a obtine o alta distributie pentru aceste numere ele trebuie trecute print-o distributie.

Toate distributiile au urmatoarele metode:

  • reset() - sterge orice valori stocate anterior, obtinute de la un motor;
  • operator() - returneaza valori (cate una la fiecare apel) intr-o anumita distributie (numere generate de un motor).

In TR1 sunt definite urmatoarele clase de distributie:

Exemple de utillizare

Cea mai simpla forma de a genera numere aleatoare este de a folosi un generator. Exemplul de mai jos foloseste unul liniar congruent pentru a genera 10 numere aleatoare. Aceste numere sunt distribuite uniform in domeniul intreg.

// generator liniar congruent
std::tr1::minstd_rand gen;

// initializare generator
gen.seed((unsigned int)time(NULL));

// generare numere
for(int i = 0; i < 10; ++i)
{
   std::cout << gen() << " ";
}
std::cout << std::endl;

In lipsa initializari, intotdeauna secventa va arata astfel:

48271 182605794 1291394886 1914720637 2078669041 407355683 1105902161 854716505 564586691 1596680831

Daca am vrea sa generam numere in intervalul [0, 9], atunci putem aplica un modulo 10 pe numerele generate.

for(int i = 0; i < 10; ++i)
{
   std::cout << gen() % 10 << " ";
}

Acelasi efect, o secventa de 10 numere aleatoare in intervalul [0, 9], uniform distribuite poate fi obtinuta folosind generatorul combinat cu o distributie uniforma.

// generator liniar congruent
std::tr1::minstd_rand gen;

// distributie uniforma
std::tr1::uniform_int<int> dist(0, 9);

// initializare generator
gen.seed((unsigned int)time(NULL));

// generare numere
for(int i = 0; i < 10; ++i)
{
   std::cout << dist(gen) << " ";
}
std::cout << std::endl;

O alta posibilitate este asocierea unui generator si a unei distributii prin clasa variate_generator.

// generator liniar congruent
std::tr1::minstd_rand gen;

// distributie uniforma
std::tr1::uniform_int<int> dist(0, 9);

// initializare generator
gen.seed((unsigned int)time(NULL));

// asociere generator-distributie
std::tr1::variate_generator<
   std::tr1::minstd_rand,
   std::tr1::uniform_int<int>> combgen(gen, dist);

// generare numere
for(int i = 0; i < 10; ++i)
{
   std::cout << combgen() << " ";
}
std::cout << std::endl;

Daca initializarea generatorului s-ar fi facut dupa definirea lui combgen atunci secventa de numere ar fi fost intotdeauna aceiasi.

// asociere generator-distributie
std::tr1::variate_generator<
   std::tr1::minstd_rand,
   std::tr1::uniform_int<int>> combgen(gen, dist);

// initializare generator
gen.seed((unsigned int)time(NULL));
0 6 8 9 1 5 3 2 7 0

Motivul este ca se face o copie a generatorului la instantierea lui combgen. Daca insa tipul generatorului ar fi unul referinta, atunci initializarea se poate face si dupa, intrucat se trimite o referinta.

// asociere generator-distributie
std::tr1::variate_generator<
   std::tr1::minstd_rand&,
   std::tr1::uniform_int<int>> combgen(gen, dist);

// initializare generator
gen.seed((unsigned int)time(NULL));

La fel ar sta lucrurile si in cazul unui tip pointer:

// asociere generator-distributie
std::tr1::variate_generator<
   std::tr1::minstd_rand*,
   std::tr1::uniform_int<int>> combgen(&gen, dist);

// initializare generator
gen.seed((unsigned int)time(NULL));

Daca nu se doreste ca numerele sa fie uniform distribuite, ci sa urmeze o alta distributie, de exemplu binomiala, nu trebuie decat folosit generatorul cu o instanta a acestei distributii:

// generator liniar congruent
std::tr1::minstd_rand gen;

// distributie binomiala
std::tr1::binomial_distribution<int, float> dist;

// initializare generator
gen.seed((unsigned int)time(NULL));

// generare numere
for(int i = 0; i < 10; ++i)
{
   std::cout << dist(gen) << " ";
}
std::cout << std::endl;

Urmatorul exemplu arata cum se poate folosi un generator compus. Acesta este initializat nu folosind un numar, ci un numar aleator, returnat de alt generator.

// motoare
std::tr1::minstd_rand gen1;
std::tr1::mt19937 gen2;
std::tr1::linear_congruential<unsigned long, 33614, 0, 2147483647> seeder;

seeder.seed((unsigned int)time(NULL));

// motor combinat
std::tr1::xor_combine<
   std::tr1::minstd_rand, // primul motor
   7, // valoare de shiftare pentru primul motor
   std::tr1::mt19937, // al doilea motor
   13 // valoarea de shiftare pentru al doilea motor
   > xorgen(gen1, gen2);

// distributie exponentiala
std::tr1::exponential_distribution<float> expdist(2);

// initializare generator
xorgen.seed(seeder);

// generare numere
for(int i = 0; i < 10; ++i)
{
   std::cout << xorgen() << " ";
}
std::cout << std::endl;

Concluzii

Clasele introduse in TR1 largesc mult posibilitatile de generare a numerelor aleatoare, cu o anumita distributie. Daca inainte erati nevoiti sa folositi o bibiloteca separata pentru a genera astfel de numere, acum aceste generatoare sunt disponibile in biblioteca standard. In plus, modalitatea de folosire a lor este destul de simpla si asemanatoare cu cea a lui rand().