Czy Fortuna lub Mersenne Twister są preferowane jako algorytmiczne RNG?

19

Ostatnia odpowiedź wspomniała o zastosowaniu generatorów liczb losowych Fortuna lub Mersenne Twister ( RNG ) do zaszczepienia symulacji Monte Carlo . Nie słyszałem o Fortunie, więc spojrzałem na nią - wygląda na to, że jest przeznaczona głównie do użytku kryptograficznego.

Obecnie używam Mersenne Twister w kodzie produkcyjnym do uruchomienia algorytmu K-Means.

Który (Fortuna lub Mersenne Twister) jest uważany za najlepszy do zastosowań w „wysiewie algorytmicznym” (np. W wysiewie Monte Carlo i K-Means)? A może jest to „podrzucanie” - czyli używanie najwygodniejszego.

Z miejsca, w którym siedzę, „najlepszy” powinien zapewniać losowe liczby najwyższej jakości, działać szybko i (ewentualnie) mieć mało pamięci. Spośród nich jakość jest prawdopodobnie najważniejsza dla większości z nas.

algorithms random-number-generation

— winwaed
źródło

6

Kryptograficzne programy PRNG są zwykle wolniejsze niż większość innych programów PRNG; jeśli wykonujesz symulację Monte Carlo, w której liczba operacji PRNG w milionach, metody kryptograficzne będą okropnie drogie.

— JM

1

@JM - Z odrobiną więcej szczegółów uważam, że Twój komentarz byłby dobry jako odpowiedź. Z pewnością interesujące byłoby sprawdzenie, czy nowoczesna sprzętowa funkcja kryptograficzna może być wykorzystana do stworzenia wysokowydajnego strumienia kryptograficznie bezpiecznych pseudolosowych liczb.

— Mark Booth,

@JM dobra uwaga na temat powolności kryptograficznych RNG - znak przeciwko Fortunie

— wygrane

Oto dobra lista PRNG i wiele różnych statystyk, które mogą ci się przydać. Mam nadzieję, że to pomoże> boost.org/doc/libs/1_48_0/doc/html/boost_random/…

— pyCthon

Moim problemem z cstdlib była ziarnistość - tylko RAND_MAX=32768możliwe wartości. Obecnie używam MT do symulacji raytracingu w Monte Carlo. Jednak nie widzę MT jako wąskiego gardła wydajności w moim programie profilującym, prawdopodobnie dlatego, że robię „losowe” generowanie rzeczy takich jak kierunki promieni jako proces wstępny . Na przykład mogę wygenerować tablicę 100 000 promieni podczas uruchamiania, przechowywać je w tablicy i losowo wybrać pozycję początkową tablicy w czasie wykonywania (uruchamianie dla około 10 000 promieni z kolekcji). Ma to stosunkowo wysoki narzut pamięci w zamian za dobre rozkłady liczb losowych.

— bobobobo

14

Cóż, wszystko jest kompromisem w taki czy inny sposób. W przypadku generatorów liczb losowych pogrupowałem je w 3 podstawowe kategorie:

Wystarczająco dobry do odrabiania lekcji.
Wystarczająco dobry, aby postawić na swoją firmę.
Wystarczająco dobry, aby postawić swój kraj.

Liniowe przystające PRNG (metoda ogólnie stosowana w większości bibliotek) są solidnie w kategorii 1. Zarówno Fortuna, jak i Mersenne Twister są solidnie w kategorii 2.

Ciekawy artykuł na temat tego, jak bałagan w algorytmie tasowania może kosztować Twoją firmę / kasyno, polecam ten z 1999 roku . Z powodu zgnilizny łącza obrazy zniknęły, ale rysunek 4, w którym wykreślasz kolejną liczbę z PRNG w stosunku do poprzednio wygenerowanej liczby, to zestaw równoległych linii.

Jak zauważa JM, Fortuna jest powolna. Jak już zauważyłeś, Mersenne Twister jest dość szybki.

— Tangurena
źródło

2

Szybko przeglądając wersję artykułu do wydrukowania , „rysunek 4” wydaje się być kodem zamiast obrazu. „Rysunek 5” wygląda kaput, ale to jest obraz, który otrzymałem z WayBack Machine .

— JM

Dzięki. wygląda na to, że prędkość jest w tym przypadku znakiem przeciwko Fortunie. Re. Złe tasowania: tak, wiem wystarczająco dużo (niewiele!), Że łatwo jest „cofnąć” losowość RNG - na przykład wybierając zły początek.

— Winwaed

Inna wersja z lepszymi zdjęciami znajduje się na stronie: cigital.com/papers/download/developer_gambling.php

— Tangurena

1

96-bitowe LCG z 32-bitowymi wyjściami przechodzą więcej testów statystycznych niż Mersenne Twisters. W dzisiejszych czasach nikt nie powinien używać Twistera Mersenne, ponieważ tak łatwo jest tworzyć przyzwoite niekryptograficzne PRNG, które są znacznie lepsze niż MT pod każdym znaczącym względem.

— Veedrac

4

Myślę, że domyślnym wyborem w kategorii „kryptograficznej” jest Blum-Blum-Shub . Jak już napisano na stronie wikipedia, nie jest to odpowiednie do symulacji, ponieważ jest zbyt cholernie wolne.

Jeśli korzystasz z systemu uniksowego, możesz również rozważyć pobranie liczb losowych bezpośrednio z / dev / urandom , usługi systemu operacyjnego, która zapewnia dobrej jakości (choć niekoniecznie krypto) liczby losowe. W zależności od konkretnego używanego systemu operacyjnego może to wykorzystywać algorytm Yarrow - którego wariantem jest Fortuna. Ale najciekawszym aspektem jest to, że system operacyjny ma dostęp do niektórych prawdziwych liczb losowych: na przykład hałasu termicznego z wewnętrznych czujników temperatury. Zazwyczaj dane te są mieszane w losowej puli, gdy tylko stają się dostępne, aby dane były nieprzewidywalne.

Ta koncepcja mieszania losowości sugeruje, że możliwe jest uzyskanie tego, co najlepsze z obu światów w następujący sposób. Używaj szybszego generatora liczb losowych o rozsądnej jakości, takiego jak Mersenne, jako podstawowego RNG. Utrzymaj także drugi, lepszej jakości generator liczb losowych - np. Fortuna. Co tyle liczb, powiedzmy 25, uruchom jedną iterację lepszego RNG i dodaj wynik do stanu podstawowego RNG. W ten sposób uzyskasz dość wysoką wydajność i dość wysoką jakość wyników. (Sądzę, że byłoby to bezużyteczne w przypadku kryptografii, ponieważ siła tego kompozytowego generatora może być siłą najsłabszego łącza. Ale w przypadku symulacji, w których zwykle nie masz złośliwego przeciwnika, może to działać).

— Erik P.
źródło

/ dev / urandom jest bezpieczny w użyciu do kryptografii na Linuksie i Free-bsd. Spójrz na tę odpowiedź

— Adam Kurkiewicz

W przypadku symulacji, dlaczego tak pożądane byłyby cechy liczb losowych? Oczywiście, niektóre generatory liczb pseudolosowych są gorsze, ale inne będą równorzędne dla wszystkich praktycznych celów. Dlaczego więc uważasz prawdziwość za dobrą cechę per se?

— Wrzlprmft

2

Chciałem powiedzieć, że niedawno przeszedłem ten proces z symulacją i powinienem zauważyć, że korzystanie z Fortuny nie wchodzi w rachubę, jeśli jest to naprawdę konieczne. W naszym przypadku obawialiśmy się, że entropia MT nie była wystarczająco wysoka, co przełożyłoby się w naszej symulacji na błąd systematyczny. Do naszej symulacji wykorzystaliśmy Fortunę, która wyciągnęła z tego algo około 65 miliardów liczb losowych. Chodzi o to, że komputery są szybkie, jeśli naprawdę potrzebujesz , możesz z niego korzystać, jeśli masz powód. Jeśli po prostu robisz coś w stylu integracji Monte Carlo, trzymaj się MT.

— tazz_ben
źródło

0

Myślę, że odpowiedź zależy w dużej mierze od aplikacji, do której zamierzasz użyć RNG. Sugerowałbym czwartą kategorię zgrubnej klasyfikacji Tangureny: „Dobra bez realnego zysku”.

W przypadku wielu aplikacji może to po prostu nie mieć znaczenia, a odpowiednio RNG o jakości kryptograficznej może po prostu spowolnić zadania bez odpowiedniego zwiększenia ważności. Na przykład wiele badań, które przeprowadzam, wymaga tylko wielu, wielu milionów liczb pochodzących w przybliżeniu z określonego przeze mnie rozkładu. Prawie każdy RNG zrobi, więc wszystko, czego potrzebuję, to taki, który nie jest tak katastrofalnie biedny, aby był bezwartościowy jak RNG. Wszystko inne po prostu niepotrzebnie spowalnia pracę. Zwykle używam Mersenne Twister, ale to po prostu dlatego, że działa wystarczająco dobrze, mam kod i jest dość szybki.

— Fomite
źródło