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.
źródło
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.Odpowiedzi:
Cóż, wszystko jest kompromisem w taki czy inny sposób. W przypadku generatorów liczb losowych pogrupowałem je w 3 podstawowe kategorie:
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.
źródło
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ć).
źródło
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.
źródło
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.
źródło