Mersenne Twister

Z Wikipedii

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 32-bitową długością słowa. Jest też wersja z 64-bitowym słowem oznaczona jako MT19937-64, która generuje inną sekwencję.

Spis treści

1 Zastosowannie
2 Zalety
3 Krytyka
4 Pseudokod
5 Przypisy
6 Odsyłacze zewnętrzne
- 6.1 Implementacje

[edytuj] Zastosowannie

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 są używane do wyznaczania ziarna dla Mersenne Twister. Jeśli potrzeba tylko kilku liczb i standardy bezpieczeństwa nie są zbyt wysokie, to prościej użyć generatora ziarnowego.

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.

[edytuj] Zalety

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

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⁶⁰⁰¹).
Wysoki stopień równomiernego rozmieszczenia. To oznacza, że okresowa zależność między kolejnymi wartościami sekwencji wyjściowej jest nieistotna.
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).

[edytuj] Krytyka

Algorytm Mersenne Twister otrzymał pewne krytyczne uwagi ze strony informatyków, szczególnie od George'a Marsaglia. Krytycy twierdzą, że choć jest doby 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ówną losowość^[2] ^[3].

[edytuj] 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
     }
 }
 
 // Pobierz pseudolosową liczbę bazując na wartości indeksu
 // przez wywołanie generateNumbers() dla każdej z 624 liczb
 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

[edytuj] Odsyłacze zewnętrzne

[edytuj] Implementacje

Kategoria: Generacja liczb losowych

We provide Linux to the World

Mersenne Twister

Z Wikipedii

Spis treści

[edytuj] Zastosowannie

[edytuj] Zalety

[edytuj] Krytyka

[edytuj] Pseudokod

Przypisy

[edytuj] Odsyłacze zewnętrzne

[edytuj] Implementacje

Views

nawigacja

zmiany

dla edytorów

Szukaj

W innych językach