Generator liczb losowych: losowanie z przetasowaniem

Niezależnie od tego, jak dobrego generatora liczb pseudolosowych używamy, zawsze chcielibyśmy, aby te liczby były jeszcze bardziej losowe.

Czytając kiedyś książkę o sieciach neuronowych natknąłem się na modyfikację standardowego generatora, która używała dodatkowej tablicy, w której przechowywane były kolejne wyniki ze standardowego generatora i z której pobierane były „losowo” wyniki owego ulepszonego generatora.

W tekście nie wyjaśniono dlaczego tak, a nie inaczej, ale dano wskazówkę, gdzie szukać. W „The Art of Computer Programming” Donalda Knutha (cz. 2) można znaleźć algorytm, który w teorii powinien polepszać losowość praktycznie rzecz biorąc dowolnego generatora liczb pseudolosowych (nawet takiego niezbyt dobrego).

Polega on na tym, że otrzymane z generatora liczby wrzuca się do tablicy o dowolnej wielkości (*), po czym się te liczby tasuje - z tym że oczywiście można to tasowanie przeprowadzać na bieżąco (por. losowanie z koszyka).

(*) - Na ogół dla wygody przyjmuje się wielkość około 100, we wspomnianej książce o sieciach neuronowych autor przyjął wielkość 97.

Opis algorytmu wygląda tak:

1. Wypełnij tablicę V[] o rozmiarze k kolejnymi liczbami pseudolosowymi.
2. Przypisz do zmiennej Y kolejną wylosowaną liczbę.
3. Wylosuj indeks j w tablicy V[]: j=k*Y/m; gdzie m - moduł w generatorze liczb pseudolosowych (maksymalna możliwa do wylosowania liczba + 1).
4. Wyciągnij z tablicy V[] element na pozycji j i przypisz do zmiennej Y: Y=V[j];
5. Wstaw na miejsce wyciągniętego elementu V[j] nową liczbę losową.
6. Zwróć liczbę losową ze zmiennej Y.

Realizacja tego algorytmu może wyglądać tak:

Uzupełnienie - w algorytm wkradł się mały błąd: zmienna y powinna być statyczna/globalna (jak sądzę). Poprawiłem, zmieniając przy okazji jej nazwę na shuffleOutput.

int shuffleTableLength=97; //taka sobie pierwsza lepsza liczba :P
int shuffleTable[shuffleTableLength];
boolean shuffleTableInitialized=false;
int shuffleOutput; //zmienna pomocnicza

int rand(void); //funkcja zwraca liczby z przedziału 0...RAND_MAX

void InitShuffleTable(void)
{
    for(int i=0; i<shuffleTableLength; ++i) shuffleTable[i]=rand();
    shuffleOutput=rand();
    shuffleTableInitialized=true;
}

int shuffleRandom(void)
{
    int j;

    /*
     * Zanim zaczniemy korzystać z algorytmu, trzeba najpierw
     * zainicjować tablicę tasującą. Dla przyspieszenia
     * można ten fragment kodu wyrzucić poza funkcję,
     * np. w jakiś konstruktor, czy na początek funkcji main().
     */
    if(!shuffleTableInitialized) InitShuffleTable();
    j=shuffleTableLength*shuffleOutput/(RAND_MAX+1);
    shuffleOutput=shuffleTable[j];
    shuffleTable[j]=rand();
    return shuffleOutput;
}

Algorytm jest szybki i prosty, i nie powinien spowalniać zbytnio generowania liczb pseudolosowych. Jak już wspomniałem, może być stosowany nawet z kiepskimi generatorami, ale nie polepszy on znacząco losowości otrzymywanych w taki sposób liczb. Można go też łatwo przerobić dla liczb pseudolosowych innych niż całkowite.

Algorytm powinien wydłużać okres generatora losowego, a nawet polepszać jego losowość, co w niektórych zastosowaniach może mieć krytyczne znaczenie. Do zwykłych zastosowań powinny wystarczyć jednak standardowe generatory, wbudowane w dany język programowania.

---

Źródło:

Donald E. Knuth: „The Art of Computer Programming”. Wydanie trzecie. Tom 2.