Dlaczego 1103515245 jest używany w rand?

Question

Dlaczego 1103515245 jest używany w rand?

Mówię o tej zaskakująco prostej implementacji rand() ze standardu C:

static unsigned long int next = 1;

int rand(void)  /* RAND_MAX assumed to be 32767. */
{
    next = next * 1103515245 + 12345;
    return (unsigned)(next/65536) % 32768;
}

Z tego artykułu Wikipedii wiemy, że mnożnik a (w powyższym kodzie a = 1103515245) powinien spełniać tylko 2 warunki:

{[4] } jest podzielna przez wszystkie czynniki pierwsze m.
(W naszym przypadku m = 2^32, wielkość int, więc m ma tylko jeden czynnik pierwszy = 2)
a - 1 jest wielokrotnością 4 Jeśli m jest wielokrotnością 4.
(32768 jest wielokrotnością 4, a także 1103515244)

Dlaczego wybrali tak dziwne, trudne do zapamiętania," człowieku, mam dość tych losowych liczb, napisz cokolwiek " numer, jak 1103515245?

Może są jakieś mądre powody, że ta liczba jest jakoś lepsza od drugiej?

Na przykład, dlaczego nie ustawić a = 20000000001? Jest większy, fajnie wyglądający i łatwiejszy do zapamiętania.

26

c random standards

Author: Adam Stelmaszczyk, 2011-12-20

Source

4 answers

Pamiętaj, że rand() jest przybliżeniem równomiernego rozkładu . Liczby te są używane, ponieważ zostały przetestowane, aby pokazać, że generują bardziej jednolity rozkład.

Biorąc pod uwagę mnogość par niepodpisanych liczb całkowitych w reprezentowalnym zakresie, wątpię, aby ktokolwiek spróbował ich wszystkich z wszystkimi poprawnymi nasionami. Jeśli uważasz, że masz lepszy wybór parametrów, po prostu wypróbuj! Masz kod, wystarczy wziąć pod uwagę parametry LCG i uruchomić testy. Wygeneruj kilka liczb (powiedzmy 10 milionów), Oblicz histogram wygenerowanych liczb i wykreśl, aby spojrzeć na rozkład.

Edit Jeśli jesteś zainteresowany opracowaniem generatora liczb pseudolosowych do użytku w rzeczywistych aplikacjach, polecam zapoznanie się z obszerną literaturą na ten temat. "Rada" podana powyżej jest tylko sugerowana, aby pomóc pokazać, że wybór arbitralnych "większych, fajnych i łatwiejszych do zapamiętania" parametrów LCG da Bardzo słaba Dystrybucja. /edit

Poza tym jest to funkcja biblioteczna i nigdy nie widziałem programu używającego standardowej wersji biblioteki rand() do zapamiętywania parametrów LCG.

6

Author: André Caron,
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2011-12-21 16:04:56

Wczesne obliczenia miały tendencję do zajmowania się bitami i bajtami i grały sztuczki z rejestrami, aby zminimalizować bajty kodu (przed wierszami były bajty)

Znalazłem tylko jedną rozsądną wskazówkę poniżej:

Wyjście tego generatora nie jest zbyt losowe. Jeśli użyjemy generatora próbek wymienionego powyżej, Sekwencja 16 bajtów kluczy będzie wysoce nieprzypadkowa. Na przykład, okazuje się, że niski bit każdego kolejnego wyjścia rand() będzie się zmieniał (np., 0,1,0,1,0,1, . . . ). Widzisz dlaczego? Niski bit x * 1103515245 jest taki sam jak niski bit X, a następnie dodanie 12345 po prostu odwraca niski bit. Tak więc niski bit zmienia się. To zawęża zestaw możliwych kluczy do tylko 2113 możliwości;znacznie mniej niż pożądana wartość 2128.

Http://inst.eecs.berkeley.edu/ ~ cs161 / fa08 / Notes / random. pdf

I dwie rozsądne odpowiedzi:

Improving a poor random number generator (1976) autor: Bays, Durham Bays, Carter, S D Durham

Http://en.wikipedia.org/wiki/TRNG

2

Author: Dave,
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2012-02-15 22:05:12

Ta liczba wydaje się wyjątkowa, jest tylko między dwiema liczbami pierwszymi: p.

Teraz mówiąc poważnie, aby zobaczyć, czy to dobry wybór, wystarczy spojrzeć na wyjście. Powinieneś zobaczyć bardzo różne wyniki, nawet jeśli przerzucasz jeden bit.

Zastanów się również, ile przewidywalności oczekujesz... Ta implementacja jest straszna, można rozważyć bardziej solidną, ale prostą alternatywę, jak FNV-1A.

0

Author: Ismael Luceno,
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2011-12-20 06:22:10

score 33 · Accepted Answer

Jeśli użyjesz LCG do narysowania punktów na przestrzeni wymiarowej d, będą one leżeć na co najwyżej (d!na)^¹/_d hiperplanes. Jest to znana wada LCGs.

Jeśli nie wybierzesz starannie a I m (poza warunkiem pełnej okresowości), mogą one leżeć na znacznie mniejszej liczbie płaszczyzn. Liczby te zostały wybrane przez tak zwany test widmowy .

"Test widmowy" (nazwa pochodzi z teorii liczb) to maksymalna odległość między kolejne hiperplanaty, na których leżą d-wymiarowe rozkłady wspólne. Chcesz, aby był jak najmniejszy dla jak największej liczby d, jaką możesz przetestować.

[[3]}Zobacz ten artykuł dla historycznego przeglądu na ten temat. Zauważ, że cytowany przez Ciebie generator jest wymieniony w artykule (jako ANSIC) i uznany za niezbyt dobry. Dopuszczalne są jednak 16 bitów wysokiego rzędu, ale wiele aplikacji będzie potrzebować więcej niż 32768 różnych wartości (jak zaznaczasz w komentarzach, okres rzeczywiście wynosi 2^31 -- warunki pełnej periodyczności w linku Wikipedii są chyba tylko konieczne).

Oryginalny kod źródłowy w dokumencie ANSI nie wziął 16 bitów wysokiego rzędu, dając bardzo słaby generator, który jest łatwy do niewłaściwego użycia (rand() % n jest tym, co ludzie najpierw myślą, aby narysować liczbę między 0 i n, a to daje coś bardzo nieprzypadkowego w tym przypadku).

Zobacz także dyskusję na temat LCGs w numerycznych recepturach. Cytowanie:

Co gorsza, wiele wczesnych Generatory zdarzały się szczególnie źle wybór dla m i a. jedna niesławna taka rutyna, RANDU, z = 65539 I m = 231, był przez wiele lat rozpowszechniony na komputerach mainframe IBM, i szeroko kopiowane na inne systemy. Jeden z nas wspomina jako absolwent uczeń tworzy" przypadkową " fabułę z zaledwie 11 samolotami i mówi przez konsultanta centrum komputerowego, że nadużywał generator liczb losowych: "gwarantujemy, że każda liczba jest losowa indywidualnie, ale my nie gwarantuj, że więcej niż jeden z nich jest przypadkowe."To opóźniło naszą edukację o co najmniej rok!