Mersenne Twister

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacja, szukaj

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

Nazwa generatora pochodzi od tego, ż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, generuje ona inną sekwencję.

Zastosowannie[edytuj | edytuj kod]

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ć[potrzebne źródło] 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[potrzebne źródło].

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[edytuj | edytuj kod]

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

  1. Okres 219937 − 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 219937 unikalnych kombinacji (219937 to w przybliżeniu 4,315425 × 106001).
  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[edytuj | edytuj kod]

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 1033000, jest znacząco szybszy i zachowuje lepszą lub równą losowość[2][3].

Pseudokod[edytuj | edytuj kod]

Poniższy pseudokod generuje 32-bitowe liczby całkowite z przedziału [0, 232 − 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
         }
     }
 }

Przypisy

Linki zewnętrzne[edytuj | edytuj kod]