Czy 161803398 to „specjalny” numer? Wewnątrz Math.Random ()

Podejrzewam, że odpowiedź brzmi `` z powodu matematyki '', ale miałem nadzieję, że ktoś mógłby dać trochę więcej wglądu na podstawowym poziomie ...

Grzebałem dzisiaj w kodzie źródłowym BCL, przyglądając się, jak niektóre z klas, których używałem wcześniej, zostały faktycznie zaimplementowane. Nigdy wcześniej nie myślałem o tym, jak generować (pseudo) losowe liczby, więc postanowiłem zobaczyć, jak to się robi.

Pełne źródło tutaj: http://referencesource.microsoft.com/#mscorlib/system/random.cs#29

private const int MSEED = 161803398; 

Ta wartość MSEED jest używana za każdym razem, gdy klasa Random () jest inicjowana.

W każdym razie widziałem tę „magiczną liczbę” - 161803398 - i nie mam pojęcia, dlaczego ta liczba została wybrana. Nie jest to liczba pierwsza ani potęga 2. Nie jest to „połowa” liczby, która wydawała się bardziej znacząca. Spojrzałem na to w systemie binarnym i heksadecymalnym i cóż, po prostu wyglądał jak liczba.

Próbowałem wyszukać numer w Google, ale nic nie znalazłem.

Nie, ale opiera się na Phi („złoty podział”).

161803398 = 1.61803398 * 10^8 ≈ φ * 10^8

Więcej o złotym podziale tutaj .

I naprawdę dobra lektura dla zwykłego matematyka tutaj .

I znalazłem artykuł badawczy dotyczący generatorów liczb losowych, który zgadza się z tym stwierdzeniem. (Patrz strona 53.)

Ta liczba pochodzi ze złotego podziału 1,61803398 * 10 ^ 8 . Matt udzielił miłej odpowiedzi, co to za liczba, dlatego tylko trochę wyjaśnię o algorytmie.

To nie jest specjalna liczba dla tego algorytmu. Algorytm jest algorytmem generatora odejmowanych liczb losowych Knutha, a jego główne punkty to:

• przechowywać okrągłą listę 56 liczb losowych
• inicjalizacja to proces wypełniania listy, a następnie losowania tych wartości za pomocą określonego algorytmu deterministycznego
• zachowane są dwa indeksy oddalone od siebie o 31
• nowa liczba losowa jest różnicą dwóch wartości przy dwóch wskaźnikach
• zapisz nową liczbę losową na liście

Generator jest oparty na następującej rekurencji: X _n = (X _n-55 - X _n-24 ) mod m, gdzie n ≥ 0. Jest to częściowy przypadek opóźnionego generatora Fibonacciego : X _n = (X _n-j @ X _n-k ) mod m, gdzie 0 <k <j i @ to dowolna operacja binarna (odejmowanie, dodawanie, xor).

Istnieje kilka implementacji tego generatora. Knuth oferuje implementację w FORTRANIE w swojej książce. Znalazłem następujący kod z następującym komentarzem:

PARAMETR (MBIG = 1000000000, MSEED = 161803398, MZ = 0, FAC = 1.E-9)

Według Knutha każdy duży MBIG i każdy mniejszy (ale nadal duży) MSEED można zastąpić powyższymi wartościami.

Nieco więcej można znaleźć tutaj. Uwaga: w rzeczywistości nie jest to praca naukowa (jak stwierdziła Math), to tylko praca magisterska.

Ludzie w kryptografii lubią używać liczby niewymierne ( pi, e, sqrt(5)), ponieważ istnieje przypuszczenie, że cyfry takich ilościach występuje z równą częstością a tym samym mają wysoką entropię . Możesz znaleźć to powiązane pytanie na temat wymiany stosów zabezpieczeń, aby dowiedzieć się więcej o takich numerach. Oto cytat:

„Jeśli stałe zostaną wybrane losowo, to z dużym prawdopodobieństwem żaden atakujący nie będzie w stanie ich złamać”. Ale kryptolodzy, będąc paranoikiem, są sceptyczni, kiedy ktoś mówi: „Użyjmy tego zestawu stałych. Przysięgam, wybrałem je na chybił trafił ”. Więc jako kompromis będą używać stałych, takich jak, powiedzmy, binarna ekspansja π. Chociaż nie mamy już matematycznej korzyści z wybierania ich losowo z jakiejś dużej puli liczb, możemy przynajmniej być bardziej pewni, że nie doszło do sabotażu.