Dlaczego Mersenne Twister jest uważany za dobry?

Mersenne Twister jest powszechnie uważany za dobry. Heck, źródło CPython mówi, że „jest jednym z najdokładniej przetestowanych generatorów na rynku”. Ale co to znaczy? Gdy poproszono mnie o podanie właściwości tego generatora, większość tego, co mogę zaoferować, jest zła:

• Jest masywny i nieelastyczny (np. Brak wyszukiwania lub wiele strumieni),
• Nie przejdzie standardowych testów statystycznych pomimo ogromnego rozmiaru stanu,
• Ma poważne problemy w okolicach 0, co sugeruje, że losuje się dość słabo,
• Nie jest szybki

i tak dalej. W porównaniu z prostymi RNG, takimi jak XorShift *, jest to również beznadziejnie skomplikowane.

Szukałem więc informacji o tym, dlaczego uważano to za dobre. Oryginalny artykuł zawiera wiele komentarzy na temat okresu „super astronomicznego” i 623-wymiarowej równomierności

Spośród wielu znanych miar testy oparte na wyższej jednorodności wymiarowej, takie jak test spektralny (por. Knuth [1981]) i test rozkładu k, opisane poniżej, są uważane za najsilniejsze.

Ale dla tej właściwości generator jest bity licznikiem o wystarczającej długości! Nie powoduje to komentarza do lokalnych dystrybucji, na których tak naprawdę zależy Ci w generatorze (chociaż „lokalny” może oznaczać różne rzeczy). Nawet CSPRNG nie przejmują się tak dużymi okresami, ponieważ po prostu nie jest to ważne.

W gazecie jest dużo matematyki, ale o ile wiem niewiele, w rzeczywistości dotyczy jakości losowości. Prawie każda wzmianka o tym szybko wraca do tych oryginalnych, w większości bezużytecznych twierdzeń.

Wygląda na to, że ludzie wskoczyli na ten modę kosztem starszych, bardziej niezawodnych technologii. Na przykład, jeśli po prostu zwiększysz liczbę słów w LCG do 3 (znacznie mniej niż „tylko 624” Mersenne Twister) i wypiszesz górne słowo za każdym razem, przekazuje BigCrush ( trudniejsza część zestawu testów TestU01 ), mimo że Twister go zawodzi ( papier PCG, ryc. 2 ). Biorąc to pod uwagę, a słabe dowody udało mi się znaleźć na poparcie Mersenne Twister, co zrobił przyczyna uwagę faworyzować ją na innych wyborów?

To też nie jest czysto historyczne. Powiedziano mi mimochodem, że Mersenne Twister jest przynajmniej bardziej sprawdzony w praktyce niż, powiedzmy, losowy PCG . Ale czy przypadki użycia są tak wymagające, aby mogły być lepsze niż nasze zestawy testów? Niektórzy Googling sugerują, że prawdopodobnie nie.

Krótko mówiąc, zastanawiam się, w jaki sposób Mersenne Twister zyskał swoją powszechną pozytywną reputację, zarówno w kontekście historycznym, jak i nie tylko. Z jednej strony jestem oczywiście sceptyczny co do jego zalet, ale z drugiej strony trudno sobie wyobrazić, że było to całkowicie przypadkowe zdarzenie.

MT był przez kilka lat uważany za dobry, dopóki nie okazał się całkiem zły dzięki bardziej zaawansowanym testom TestU01 BigCrush i lepszym PRNG.

Tabela na pcg-random.org np. Daje dobry przegląd funkcji niektórych z najczęściej używanych PRNG, gdzie jedyną „dobrą” cechą Mersenne Twister jest ogromny okres, i możliwość użycia seed (Powtarzalne wyniki), przechodzi proste i szybkie testy TestU01 SmallCrush, ale nie spełnia niektórych nowszych statystycznych testów jakości, szczególnie. Test LinearComp TestU01 oraz baterie Crush i BigCrush TestU01.$2^{219937}$

Ta strona zawiera szczegółowe informacje na temat funkcji Mersenne-Twister:

Pozytywne cechy

• Tworzy liczby 32-bitowe lub 64-bitowe (dzięki czemu można je wykorzystywać jako źródło losowych bitów)
• Przechodzi większość testów statystycznych

Neutralne cechy

• okres$2^{219937} - 1$
• 623-równomiernie rozłożony
• Okres można podzielić na partycje, aby emulować wiele strumieni

Negatywne cechy

• Nie udaje się przeprowadzić niektórych testów statystycznych z zaledwie 45 000 liczb.
• Przewidywalne - po 624 wyjściach możemy całkowicie przewidzieć jego wydajność.
• Stan generatora zajmuje 2504 bajty pamięci RAM - w przeciwieństwie do tego niezwykle użyteczny generator z okresem, w którym każdy może kiedykolwiek użyć, zmieści się w 8 bajtach pamięci RAM.
• Niezbyt szybko.
• Niezbyt zajmujący miejsce. Generator używa 20000 bitów do przechowywania swojego stanu wewnętrznego (20032 bitów na komputerach 64-bitowych), ale ma okres tylko , czyli o 263 (lub 295) mniej niż idealny generator o tym samym rozmiarze.$2^{219937}$
• Nierówny w wydajności; generator może dostać się do „złych stanów”, z których powoli dochodzi do siebie.
• Siewki, które różnią się tylko nieznacznie, długo się od siebie różnią; siew należy wykonać ostrożnie, aby uniknąć złych stanów.
• Chociaż możliwe jest przeskok do przodu, algorytmy do tego celu są powolne do obliczenia (tj. Wymagają kilku sekund) i rzadko zapewniają je implementacje.

Podsumowanie : Mersenne Twister nie jest już wystarczająco dobry, ale większość aplikacji i bibliotek jeszcze nie istnieje.

Jestem redaktorem, który zaakceptował artykuł MT w ACM TOMS w 1998 roku i jestem również projektantem TestU01. Nie używam MT, ale głównie MRG32k3a, MRG31k3p i LRSR113. Aby dowiedzieć się więcej na ten temat, na temat MT i tego, co jeszcze jest, możesz zapoznać się z następującymi artykułami:

F. Panneton, P. L'Ecuyer i M. Matsumoto, `` Improved Long-Period Generators Based on Linear Recurrences Modulo 2 '', ACM Transactions on Mathematical Software, 32, 1 (2006), 1-16.

P. L'Ecuyer, `` Random Number Generation '', rozdział 3 Handbook of Computational Statistics, JE Gentle, W. Haerdle i Y. Mori, red., Drugie wydanie, Springer-Verlag, 2012, 35-71 . https://link.springer.com/chapter/10.1007/978-3-642-21551-3_3

P. L'Ecuyer, D. Munger, B. Oreshkin i R. Simard, `` Random Numbers for Parallel Computers: Requirements and Methods '', Mathematics and Computers in Simulation, 135, (2017), 3-17. http://www.sciencedirect.com/science/article/pii/S0378475416300829?via%3Dihub

P. L'Ecuyer, `` Generowanie liczb losowych z wieloma strumieniami dla komputerów sekwencyjnych i równoległych '', zaprosił zaawansowany samouczek, Materiały z konferencji Winter Simulation Conference 2015, IEEE Press, 2015, 31-44.

Podobnie jak algorytmy sortowania w tym względzie, nie ma „jednego rozmiaru dla wszystkich” PRNG. Różne są wykorzystywane do różnych celów i istnieje wiele różnych kryteriów projektowych i zastosowań. Możliwe jest niewłaściwe zastosowanie PRNG, na przykład użycie jednego do kryptografii, do którego nie jest przeznaczony. Wpis Wikipedii na temat Mersenne Twister wspomina również, że nie został on zaprojektowany do „symulacji Monte-Carlo, które wymagają niezależnych generatorów liczb losowych”.

Jak wspomniano na Wikipedii, ten PRNG jest rzeczywiście używany w wielu językach programowania i aplikacjach, nawet jako domyślny PRNG. W celu wyjaśnienia, dlaczego jeden PRNG jest preferowany, potrzebna byłaby analiza niemal socjologiczna. Niektóre możliwe czynniki, które mogą przyczynić się do powstania tego PRNG:

• Autor ma dobre / silne kwalifikacje naukowe w tej dziedzinie i pracuje w PRNG od dziesięcioleci.

• Został specjalnie zaprojektowany, aby być lepszy od innych metod w tym czasie.

• Autor jest zaangażowany we wdrażanie i śledzenie ich, a także przyczynia się do nich. Niektóre PRNG są bardziej teoretyczne, a autorzy nie zawsze zajmują się rzeczywistymi wdrożeniami.

• System jest dobrze obsługiwany / aktualizowany na stronie internetowej.

• Opracowano nowe wersje PRNG, aby radzić sobie z niedociągnięciami. Nie ma jednego algorytmu Mersenne Twister, bardziej przypomina on różne wersje i rodzinę wariantów, które mogą obsługiwać różne potrzeby.

• Zostało ono szczegółowo przeanalizowane / przetestowane przez standardowe oprogramowanie do analizy losowości i przekazane przez niezależne organy.

• Znany jest efekt mierzony w przypadku witryn internetowych i wielu innych kontekstów, takich jak cytaty naukowe zwane „preferencyjnym przywiązaniem”, które można zmierzyć. Zasadniczo to od dawna znane źródła historyczne są wykorzystywane w większym stopniu. Taki efekt może z czasem wyjaśniać wybory PRNG.

Innymi słowy, pytasz o zjawisko „popularności”, które jest powiązane i powiązane z ludzkimi wyborami i nie jest ściśle powiązane z konkretnymi cechami, ale jest rodzajem złożonej / powstającej właściwości i interakcji między różnymi algorytmami, użytkownikami i środowiskiem / konteksty użytkowania.

Oto jedna taka niezależna analiza algorytmu Mersenne Twister - Generator liczb pseudolosowych i jego warianty autorstwa Jagannatam (15p). Ostatni akapit jest zasadniczo odpowiedzią na twoje pytanie. cytując tylko kilka ^pierwszych zdań:

Teoretycznie udowodniono, że Mersenne Twister jest dobrym PRNG, z długim okresem i wysoką równomiernością dystrybucji. Jest szeroko stosowany w dziedzinie symulacji i modulacji. Wady wykryte przez użytkowników zostały naprawione przez wynalazców. MT został zaktualizowany, aby używać i być kompatybilnym z nowo powstającymi technologiami procesorów, takimi jak SIMD i równoległe potoki w swojej wersji SFMT.