Mersenne Twister

Mersenne Twister – algorytm generatora liczb pseudolosowych opracowany w 1997 przez Makoto Matsumoto i Takuji Nishimura. Generator jest szybki i dostarcza wysokiej jakości liczby pseudolosowe. Został zaprojektowany specjalnie w celu uniknięcia wielu wad, które znajdują się w starszych algorytmach.

Nazwa generatora pochodzi od faktu, że na długość okresu wybierana jest liczba pierwsza Mersenne’a. Istnieją co najmniej dwa warianty algorytmu, które różnią się jedynie wielkością użytych liczb pierwszych Mersenne’a. Nowszy i bardziej rozpowszechniony jest Mersenne Twister z oznaczeniem MT19937 – ma on 32-bitową długość słowa. Jest też wersja z 64-bitowym słowem oznaczona jako MT19937-64, lecz generuje ona inną sekwencję.

Zastosowanie

Inaczej niż Blum Blum Shub algorytm w swej podstawowej postaci nie nadaje się do kryptografii. Obserwacja wystarczającej liczby iteracji (624 dla MT19937) pozwala przewidzieć wszystkie kolejne.

Inną kwestią jest długi czas, który może zabrać przestawienie nielosowego stanu początkowego w stan wyjściowy, który spełnia testy losowości. Prosty generator Fibonacciego lub liniowy generator kongruencyjny startują dużo szybciej i mogą być używane do wyznaczania ziarna dla Mersenne Twister.

Dla wielu innych zastosowań Mersenne Twister jest szybki. Ponieważ biblioteka jest przenośna, łatwo dostępna i szybko generuje dobrej jakości liczby pseudolosowe, to jej użycie rzadko jest złym wyborem.

Generator został zaprojektowany z myślą o metodach Monte Carlo i innych symulacjach statystycznych. Badacze przede wszystkim potrzebują dobrej jakości liczb, ale skorzystają też z jego szybkości i przenośności.

Zalety

Powszechnie używany wariant MT19937 Mersenne Twistera posiada następujące pożądane właściwości:

1. Okres 2¹⁹⁹³⁷ − 1 (twórcy algorytmu udowodnili tę własność). W praktyce jest mało powodów by używać większego, bo większość zastosowań nie wymaga 2¹⁹⁹³⁷ unikalnych kombinacji (2¹⁹⁹³⁷ to w przybliżeniu 4,315425 × 10⁶⁰⁰¹).
2. Wysoki stopień równomiernego rozmieszczenia. To oznacza, że okresowa zależność między kolejnymi wartościami sekwencji wyjściowej jest nieistotna.
3. Spełnia liczne testy statystycznej losowości, włączając w to testy diehard. Spełnia większość, choć nie wszystkie, bardziej rygorystycznych testów losowości (TestU01 Crush).

Krytyka

Algorytm Mersenne Twister otrzymał pewne krytyczne uwagi ze strony informatyków, szczególnie od George’a Marsaglia. Krytycy twierdzą, że choć jest dobry w generowaniu liczb pseudolosowych, to nie jest zbytnio elegancki i jest nazbyt skomplikowany w implementacji. Marsaglia podał kilka przykładów generatorów, które są mniej złożone i jak twierdzi mają znacząco większe okresy. Na przykład generator dopełniający mnożenie z przeniesieniem może mieć dłuższy okres – 10³³⁰⁰⁰ – jest znacząco szybszy i zachowuje lepszą lub równie dobrą losowość.

Pseudokod

Poniższy pseudokod generuje 32-bitowe liczby całkowite z przedziału [0, 2³² − 1] za pomocą algorytmu MT19937.

// Utwórz tablicę 624 elementów do przechowywania stanu generatora
 int[0..623] MT
 int index = 0
 
 // Inicjuj generator przy użyciu ziarna
 function initializeGenerator(int seed) {
     MT[0] := seed
     for i from 1 to 623 { // pętla po każdym elemencie
         MT[i] := last 32 bits of(1812433253 * (MT[i-1] xor (right shift by 30 bits(MT[i-1]))) + i) // 0x6c078965
     }
 }
 
 // Utwórz pseudolosową liczbę na podstawie indeksu,
 // wywołaj generateNumbers() aby utworzyć nową tablicę pomocniczą co 624 liczby
 function extractNumber() {
     if index == 0 {
         generateNumbers()
     }
     
     int y := MT[index]
     y := y xor (right shift by 11 bits(y))
     y := y xor (left shift by 7 bits(y) and (2636928640)) // 0x9d2c5680
     y := y xor (left shift by 15 bits(y) and (4022730752)) // 0xefc60000
     y := y xor (right shift by 18 bits(y))
     
     index := (index + 1) mod 624
     return y
 }
 
 // Generuj tablicę 624 liczb
 function generateNumbers() {
     for i from 0 to 623 {
         int y := 32nd bit of(MT[i]) + last 31 bits of(MT[(i+1) mod 624])
         MT[i] := MT[(i + 397) mod 624] xor (right shift by 1 bit(y))
         if (y mod 2) == 1 { // y is odd
             MT[i] := MT[i] xor (2567483615) // 0x9908b0df
         }
     }
 }

Linki zewnętrzne

• Praca naukowa o Mersenne Twister oraz powiązane artykuły Makoto Matsumoto
• Strona domowa Mersenne Twister z kodem w C, Fortranie, Javie, Lispie i innych językach
• SIMD-oriented Fast Mersenne Twister (SFMT)