Jak już pisałem w pierwszej części serii o generatorach, tym razem opiszę generator liczb pseudolosowych o rozkładzie równomiernym.

Rozkład równomierny dla zmiennej losowej ciągłej na podanym przedziale [a,b] oznacza, że prawdopodobieństwo wystąpienia każdej z wartości w tym przedziale jest dokładnie takie samo i wynosi dokładnie 1/(b-a) - stąd widać, że a i b muszą być wartościami skończonymi, aby wynik był sensowny. Prawdopodobieństwo wystąpienia każdej wartości spoza przedziału wynosi 0. Analogicznie sytuacja ma się dla zmiennej losowej dyskretnej. Przykładem dla dyskretnej zmiennej losowej może być rzut monetą lub kostką sześcienną ( zakładając, że nie są w jakiś sposób zmodyfikowane ). Więcej teorii łatwo znaleźć na wikipedii - ten wpis nie ma na celu wykładu matematycznego.

Zajmijmy się teraz właściwym tematem czyli generatorami. Pomysłów na generatory liczb o takim rozkładzie było w historii kilka. Przedstawię tutaj dwa z nich: generator mieszany oraz multiplikatywny.

Generator mieszany opiera się na prostym wzorze matematycznym:

X_(n+1) = ( a*X_n + c ) mod m

Przy założeniu, że a, c, m > 0. Te współrzynniki powinny być odpowiednio dobrano, przy czym kryteria są następujące:

• okres generatora powinien być możliwie długi
• jak największe złudzenie losowości

Pierwszy aspekt jest w miarę oczywisty natomiast w drugim, chodzi o to, że patrząc na wygenerowane liczby nie można zauważyć wzoru, który je generuje. Powiedzmy, że mamy 3 możliwe wartości do wylosowania: 1, 2 i 3. Wygenerowane wartości mogą wyglądać tak: 1 1 1 2 2 2 3 3 3 1 itd. widać, że rozkład jest równomierny, ale losowość żadna. Wracając do pierwszego kryterium, aby je spełnić trzeba trzymać się następujących zasad:

• współczynniki c i m powinny być liczbami wzajemnie pierwszymi
• a = 1 mod p dla każdego czynnika pierwszego p liczby m

Patrząc na wzór matematyczny, można dostrzec, że może być problem z jego implementacją tak, aby uzyskać najdłuższy możliwy okres na maszynie 32-bitowej czyli 2147483647. Wiąże się to z przepełnieniem w czasie dokonywania obliczeń. Powstał więc algorytm, który zapobiega takiemu obrotowi sprawy i implementuje wcześniejszy wzór dla c = 0. Oto on:

1. h := floor( X/q )
2. X = a*( X - q*h ) - r*h
3. jeśli X < 0 to X = X + 2147483647

Oczywiście X jest wynikiem. Na potrzeby implementacji zostały opracowane trójki liczb, które spełniają wcześniej ustalone kryteria, poniżej trzy takie przykładowe trójki:

• a = 16807 q = 127773 r = 2836
• a = 48271 q = 44488 r = 3399
• a = 69621 q = 30845 r = 23902

Czas na przykładową implementację w C++. Zacznę od klasy abstrakcyjnej, którą napisałem na potrzeby tworzonego projektu:

class Generator
{
public:
virtual double NextValue() = 0;
};

Jako, że w C++ nie ma typowo klas abstrakcyjnych, tworzomy je poprzez zadeklarowanie wszystkich metod jako czysto wirtualne. Teraz część właściwa, czyli generator liczb o rozkładzie równomiernym:

class UniformGenerator : public Generator
{
public:
UniformGenerator( int _seed = 1, double low = 0.0, double high = 1.0 );
double NextValue();

static const int max = 2147483647;
static const int a = 16807;
static const int q = 127773;
static const int r = 2836;
private:
int seed;
double low_level;
double high_level;
};

Widać tu statyczne stałe, które reprezentują wcześniej wspomniane współczynniki oraz wartość maksymalną. Składowe prywatne to seed czyli tzw jądro generatora, dolny i górny zakres ( czyli granice przedziału [a,b] ). Jądro generatora to X_0 czyli wartość startowa. Implementacja:

UniformGenerator::UniformGenerator( int _seed, double low , double high ): seed( _seed ), low_level( low ), high_level( high )
{

}

double UniformGenerator::NextValue()
{
int h = seed/q;
seed = a*( seed - q*h ) - r*h;
if ( seed < 0 )
seed += max;

return ( (double)seed/(double)max*( high_level-low_level ) + low_level );
}

Nie ma tu żadnych niespodzianek poza “regulacją zakresu”. Domyślnie generator wg wcześniejszego wzoru i po podzieleniu przez maksymalną wartość generuje liczby na przedziale [0,1].

Przyszedł czas na generator multiplikatywny, tym razem będzie bez implementacji w C++, dlatego, że widać ją powyżej. Generator multiplikatywny to szczególny przypadek generatora mieszanego, właśnie przy założeniu c = 0. W zasadzie nic więcej na ten temat nie trzeba mówić.

W kolejnej notce dalej będę opisywał metody generacji, jednak innych rozkładów dość powszechnie używanych.