Autor Wątek: Dobry szybki generator liczb losowych  (Przeczytany 1352 razy)

Offline Kos

  • Użytkownik
    • kos.gd

# Lipiec 31, 2011, 23:22:50
Zanim ktoś krzyknie "MT!", niech zerknie na to, o co właśnie się potknąłem: generator zarówno szybszy (i o prostszej implementacji), jak i - podobno - lepszej jakości (dużo, dużo dłuższy okres) niż MT.

Temat zamyka się w tych paru linijkach:

/* choose random initial c<809430660 and */
/* 4096 random 32-bit integers for Q[]   */
static unsigned long Q[4096],c=362436;

unsigned long CMWC4096(void) {
    unsigned long long t, a=18782LL;
    static unsigned long i=4095;
    unsigned long x,r=0xfffffffe;
    i = (i+1) & 4095;
    t = a*Q[i] + c;
    c = (t>>32);
    x = t + c;
    if (x < c) {
        x++;
        c++;
    }
    return (Q[i] = r - x);
}

Źródełko + czytanie:

http://school.anhb.uwa.edu.au/personalpages/kwessen/shared/Marsaglia03.html

W tym wątku na SO tłumaczenie na Javę.

Offline Mr. Spam

  • Miłośnik przetworów mięsnych

Offline nembutal

  • Użytkownik

# Lipiec 31, 2011, 23:42:44
Czy stan o rozmiarze
static unsigned long Q[4096]to nie jest trochę za dużo? (dużo miejsca zajmie w cache procesora)
Poza tym, okres to jeszcze nie wszystko - trzeba by jakoś zmierzyć jak równomierny jest rozkład tych liczb losowych.

Offline Kos

  • Użytkownik
    • kos.gd

# Lipiec 31, 2011, 23:57:40
Czy stan o rozmiarze
static unsigned long Q[4096]to nie jest trochę za dużo? (dużo miejsca zajmie w cache procesora)

True. Ten przykład miał chyba charakteryzować się dużym okresem, ale dokument cytuje też np. taki lżejszy wariant:

static unsigned long Q[256], c = 362436; /* choose random initial c<809430660 and */
/* 256 random 32-bit integers for Q[]    */

unsigned long MWC256(void) {
unsigned long long t, a = 809430660LL;
static unsigned char i = 255;
t = a * Q[++i] + c;
c = (t >> 32);
return (Q[i] = t);
}

Tu okres około 2^8222 (dużo mniej niż MT, lecz  dość na gamedevowe potrzeby?), ale też dużo mniejszy stan (ponad 2x mniejszy niż MT), no i podobno tym samym bardzo dobra wydajność.

Cytuj
Poza tym, okres to jeszcze nie wszystko - trzeba by jakoś zmierzyć jak równomierny jest rozkład tych liczb losowych.

Jasne. Dokument, który zacytowałem, ogranicza się tu do lakonicznego "seems to pass all tests", ale pokładam nadzieję że konkretne implementacje, które zacytowali, zostały faktycznie przetestowane pod kątem rozkładu. Możemy ofc to zweryfikować.

Offline yarpen

  • Użytkownik

# Sierpień 01, 2011, 00:14:58
Jeszcze prostszy i szybszy i tez przechodzacy wszystkie testy jest KISS (tez Marsaglii) opisany np. tutaj: http://www.cs.ucl.ac.uk/staff/d.jones/GoodPracticeRNG.pdf . OK 30 cykli na C2D.