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.

— Veedrac
źródło

Myślę, że masz rację. Mersenne Twister nie jest niczym szczególnym. Jest po prostu dobrze znany (a wiele innych znanych PRNG jest gorszych). Istnieją inne PRNG, które są również całkiem dobre. Aby uzyskać jeszcze lepszy PRNG, można użyć kryptograficznego PRNG. Nie jestem jednak pewien, jaką odpowiedź można udzielić poza „nie ma nic złego w twoim rozumowaniu”.

— DW

Myślę, że pytanie, które powinieneś zadać, nie brzmi, czy MT jest dobre (ponieważ jest, według wielu wskaźników), ale dlaczego jest częściej używane niż alternatywy, takie jak PCG lub XorShift. Odpowiedź jest prawdopodobnie taka, że jest ona dostępna już od dłuższego czasu i przez długi czas była najlepszym rozsądnym domyślnym (w latach internetowych).

— pseudonim

@vzn „Innym czynnikiem jest czas generacji;„ jakość ”PRNG odbywa się kosztem czasu pracy” → Z wyjątkiem tego, że Mersenne Twister jest wolniejszy i gorszy niż rezonansowo duża LCG. Patrz ryc. 16 w dokumencie PCG. (O tym, czy przeczytałem gazetę: Przeczytałem szczegółowo większość niematematycznych części papieru Mersenne Twister i wszystkie losowe papiery PCG. Przeważnie

— przejrzałem

Mówisz o algorytmach XorShift czy KISS?

— gnasher729,

@ gnasher729 Wspominam o XorShift *, ale tak naprawdę nie jestem specyficzny dla konkretnej alternatywy. Nie wiedziałem o KISS, FWIW.

— Veedrac

Odpowiedzi:

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.

— rurban
źródło

Dzięki za miłe podsumowanie! Obawiam się jednak, że jedynym widocznym źródłem twojego postu jest strona internetowa, która jest faktycznie reklamą dla innej rodziny generatorów liczb losowych, która nie została jeszcze sprawdzona. Sama strona internetowa nie zawiera żadnych odniesień do wpisów, ale proponowany artykuł zawiera wiele. Dlatego myślę, że możesz poprawić swoją odpowiedź na kontekst tutaj (krytyka MT), podając odniesienia do poszczególnych punktów.

— Raphael

Czy poważnie sprzeczają się, że ten okres to tylko a nie i że po stwierdzeniu, że długi okres jest „neutralną” właściwością prng?

2^{219937}

$2^{219937}$

295 \times 2^{219937} \approx 2^{219945}

$295\times 2^{219937} \approx 2^{219945}$

— David Richerby

„Przewidywalny” - MT nie jest przeznaczony do kryptograficznego PRNG, więc zredaguj swoją odpowiedź.

— Jason S

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.

— Pierre L'Ecuyer
źródło

Dzięki za odpowiedź! Czy mógłbyś dodać coś do pytania? 1) Dlaczego według ciebie MT było dobre (a przynajmniej warte opublikowania)? 2) Dlaczego nie uważasz, że jest wystarczająco dobry do użycia?

— Raphael

Dziękujemy za dodanie tego cennego kontekstu historycznego. Jestem również ciekawy pytań Raphaela i twoich osobistych przemyśleń po przyjęciu artykułu.

— Veedrac

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.

— vzn
źródło

Dzięki. Niektóre z tego, co mówisz, brzmią jednak dość niejasno, na przykład: „Zostało specjalnie zaprojektowane, aby przewyższać inne metody w tym czasie”. oraz „Zostało ono gruntownie przeanalizowane / przetestowane przez standardowe oprogramowanie do analizy losowości i przekazane przez niezależne władze”. Są to dokładnie tezy, które mnie podejrzewają. Zagłębię się jednak trochę w papier, aby zobaczyć, czy to wszystko wyjaśni.

— Veedrac

Inną rzeczą, którą należy wziąć pod uwagę, jest odtwarzalność naukowa. Wielu naukowców, którzy pracują w obszarze symulacji Monte Carlo, zadaje sobie wiele trudu, aby upewnić się, że program jako całość generuje taką samą wydajność przy tym samym nasieniu, niezależnie od liczby wątków. Wiele z nich wymaga zgodności typu błąd po błędzie z referencyjną implementacją PRNG.

— pseudonim

Mówicie także: „Opracowano nowe wersje PRNG, aby radzić sobie z niedociągnięciami”, ale biorąc pod uwagę większość implementacji, to pierwsza wersja w standardzie torfowiska, co wydaje mi się bardziej krytyką. Jestem też trochę zaskoczony, widząc „System jest dobrze obsługiwany / aktualizowany na stronie internetowej”. - ile wsparcia naprawdę potrzebuje LCG !?

— Veedrac

@Pseudonim, którego tak naprawdę nie śledzę. Dlaczego miałoby to wykluczać używanie innego generatora? Oczywiście przy ponownym uruchamianiu testów należy używać tego samego generatora, ale po co nowe testy?

— Veedrac

nie wydaje się wiele niejasności w całej analizie naukowej w oryginale i kolejnych artykułach, a oryginalne pytanie jest w pewien sposób „wczytane” w ten sposób (afaik wykorzystuje wiele PRNG o mniejszej analizie / wsparciu). re Pseudonimy wskazują, że wszystkie PRNG są powtarzalne przy użyciu tych samych początkowych nasion, tylko sprzętowe generatory nie są (i tak naprawdę nie są już PRNG, ale „prawdziwy fizyczny szum / losowość”). nie jestem pewien, jak to jest rzekomo trudne do zapewnienia z wieloma wątkami (nie wiem, dlaczego osobne wątki nie mogą używać identycznego algorytmu z różnymi nasionami)

— vzn