Próbowałem rozwiązać problem hobby, który wymagał wygenerowania miliona losowych liczb. Ale szybko zdałem sobie sprawę, że trudno jest uczynić je wyjątkowymi. Wziąłem instrukcję projektowania algorytmów, aby przeczytać o generowaniu liczb losowych.
Ma następujący akapit, którego w pełni nie rozumiem.
Niestety generowanie liczb losowych wygląda o wiele łatwiej niż jest w rzeczywistości. Rzeczywiście, generowanie liczb losowych na dowolnym urządzeniu deterministycznym jest zasadniczo niemożliwe. Von Neumann [Neu63] powiedział to najlepiej: „Każdy, kto rozważa arytmetyczne metody tworzenia losowych cyfr, jest oczywiście w stanie grzechu.” Najlepsze, na co możemy liczyć, to liczby pseudolosowe, strumień liczb, które wyglądają jak jeśli zostały wygenerowane losowo.
Dlaczego niemożliwe jest uzyskanie prawdziwie losowych liczb w jakimkolwiek deterministycznym urządzeniu? Co oznacza to zdanie?
źródło
Odpowiedzi:
Należy szukać kryptograficznie bezpiecznego generatora liczb pseudolosowych . Większość PRNG to liniowe generatory zgodności (więc
next number
jest to funkcja liniowaprevious number
), więc jeśli narysujesz wykresnext number
vsprevious number
otrzymasz wykres równoległych linii. CSPRNG tego nie zrobi. Kompromis polega na tym, że są one powolne.Generatory liczb losowych dzielę na 3 kategorie :
Deterministyczne urządzenie zawsze będzie wytwarzało tę samą moc wyjściową, jeśli otrzyma takie same warunki początkowe i dane wejściowe - tak właśnie powinno być
deterministic
. „Prawdziwie losowa liczba” jest bardziej filozoficznym punktem widzenia, ponieważ to, co oznacza być,random
stanowi sedno filozoficznego patrzenia na pępek (ludzie nie są nawet pewni, czy rozpad atomowy jest losowy lub przebiega według jakiegoś wzoru, którego po prostu nie możemy zrozumieć jeszcze). Kryptograficznie bezpieczny generator liczb losowych pobierze jakieś zewnętrzne źródło entropii, aby urządzenie nie było deterministyczne.źródło
Prawdziwa przypadkowość implikuje niedeterminizm. Jeśli jest deterministyczny, można go dokładnie przewidzieć (to właśnie oznacza determinizm); jeśli można to przewidzieć, nie jest losowy.
Najlepszą rzeczą, jaką można uzyskać od deterministycznego generatora liczb pseudolosowych, jest strumień liczb, który ma bardzo długi cykl (niepowtarzanie się jest niemożliwe, chyba że urządzenie RNG ma nieograniczoną pamięć), które przez cały cykl daje liczby strumieni spełniające wszystkie pozostałe właściwości losowej sekwencji (najbardziej interesujący jest jednolity rozkład wartości).
Aby rozwiązać ten problem, wiele współczesnych uniksów i systemów uniksowych ma RNG jądra, które wykorzystują fizyczne źródła hałasu do generowania prawdziwej losowości.
Innym powszechnym podejściem jest przyjmowanie bieżącego czasu jako zalążka deterministycznego RNG (
srand(time(NULL));
w C); kryptograficznie rzecz biorąc, jest to bezwartościowe, ponieważ obecny czas nie jest tajemnicą, ale w przypadku takich rzeczy, jak symulacje fizyczne lub gry wideo, jest wystarczająco dobry.źródło
Drugi rozdział książki Discrete-Event Simulation: A First Course autorstwa Lawrence'a Leemisa stanowi fantastyczne wprowadzenie do generatorów liczb losowych (a ściślej - generatorów liczb losowych psuedo).
Fragment jego książki wyjaśnia to dobrze moim zdaniem:
Tak więc chociaż możliwe byłoby użycie generatora szumów białych w celu uzyskania „lepszych” liczb losowych, nie zyskały one akceptacji, ponieważ nie spełniają większości powyższych kryteriów.
Radziłbym, abyś dostał kopię tej książki (lub czegoś podobnego). Zrozumienie, w jaki sposób praca PRNG z pewnością pomoże ci w twoich wysiłkach.
źródło
Ponieważ musisz napisać kod, aby wygenerować losowe liczby, a kod NIE jest losowy. (To deterministyczne)
Więc zaczynasz od „Wartości początkowych”, które są wybierane jako „Losowo” (zwykle aktualny znacznik czasu), a następnie używasz go w algorytmie, aby zacząć generować liczby. Ale cały zestaw oparty jest na oryginalnej wartości Seed!
Więc jeśli ponownie uruchomisz kod z dokładnie tymi samymi wartościami nasion, otrzymasz DOKŁADNY ten sam ZESTAW liczb! Jak każda rozsądna osoba może nazwać to przypadkiem? Ale to na pewno nie LOOK losowy.
Jeśli chodzi o uczynienie ich wyjątkowymi, po wygenerowaniu numeru po prostu sprawdź, czy już go masz, jeśli tak, wyrzuć go i wygeneruj nowy.
źródło
Ponieważ generujesz liczby losowe, należy oczekiwać, że wygenerowane wartości będą niejednoznaczne. Jest to właściwość losowości - nie można powiedzieć, że sekwencja liczb prawdziwie losowych (lub nawet pseudolosowych) jest unikalna, ponieważ wymaganie to pozwoliłoby przewidzieć końcową wartość w zakresie, a także zmienić prawdopodobieństwo wszystkie niezaznaczone liczby za każdym razem, gdy wybierany jest nowy.
źródło
Mam bardzo prostą definicję Pseudo Random :
Zbyt wiele nieznanych zmiennych do przewidzenia.
Mam również prostą definicję True Random :
Nieskończone nieznane zmienne.
Problem z komputerem polega na tym, że zawsze zna WSZYSTKIE zmienne. Liczba losowa jest po prostu funkcją matematyczną o pewnej wartości początkowej .
Najlepsze, co możemy zrobić, to podać komputerowi pseudolosową wartość początkową, która zwykle opiera się na zmiennej, której nie jesteśmy w stanie przewidzieć (takiej jak dokładny czas).
Mimo że komputer absolutnie nie jest w stanie utworzyć liczby losowej, dobrze jest wprowadzić zbyt wiele zmiennych, aby można było przewidzieć!
źródło
Generowanie prawdziwie losowych liczb w oprogramowaniu nie jest w rzeczywistości możliwe, jak zauważyli inni, jednak możliwe jest zbudowanie przez sprzęt urządzenia, które może generować prawdziwie losowe liczby *. Istnieje wiele takich przykładów w Internecie i istnieje wiele różnych metod, od odczytu czasu pomiędzy tyknięciami na liczniku Geigera do próbkowania białego szumu (głównie promieniowania tła z wszechświata) nieregulowanego odbiornika. Sam zbudowałem kilka przy użyciu kilku dostępnych metod.
* Każdy dobry maniak fizyki zwróci uwagę, że biorąc pod uwagę sposób działania wszechświata, żaden z nich nie jest naprawdę technicznie losowy, ale nie ma rozsądnego sposobu przewidzenia wyników, więc ze względu na tę dyskusję są wystarczające.
źródło
Nie ma możliwości wyprodukowania losowej liczby bez specjalnego sprzętu. W pierwszym roku studiów, z kilkoma kolegami z klasy, zaproponowaliśmy generator liczb losowych, który ma w zasadzie odbiornik AM i dostroił się do 4 różnych kanałów, dostał dane wejściowe do konwertera A na D i dodał je wszystkie (modulo do maksymalnej liczby). Ponieważ kombinacja wejścia analogowego z dowolnej dowolnej liczby stacji jest losowa i moglibyśmy wygenerować dużą liczbę liczb losowych z konwertera A2D, zaproponowaliśmy, że może to być dobry generator. Oczywiście nawet to nie jest przypadkowe w sensie filozoficznym, choć dla większości praktycznych celów może to zadziałać.
źródło
Determinizm jest zasadniczo funkcją. Pamiętaj z Algebry, że funkcja jest zgodnością między domeną i zakresem, że każdy członek domeny odpowiada dokładnie jednemu członkowi zakresu.
Więc jeśli f (x) = z, f (x)! = Y, chyba że y jest z. To jest funkcja. Wyobraź sobie JavaScript:
Bez względu na to, ile razy wywołasz
Add(2,3)
, zawsze zwróci 5. Innymi słowy, Add () jest funkcją deterministyczną.Czynniki zewnętrzne mogą powodować, że Add zachowuje się w sposób niedeterministyczny. Na przykład, jeśli wprowadzisz wielowątkowość do równania. Wkład człowieka powoduje również niedeterminizm.
Teraz rzeczy stają się interesujące.
Uwaga Von Neumann stwierdza: „arytmetyczne metody wytwarzania [...]”. Nie chodzi tu o wkład człowieka, współbieżność, przykładowe prędkości wiatru odczytane z precyzyjnego przyrządu lub inne nie algorytmiczne sposoby generowania losowego sygnału wejściowego do funkcji deterministycznej.
To po prostu stwierdza, że funkcja lub system funkcji nie stanie się nagle niedeterministyczny. Innymi słowy, Add (2,3) nie zwróci w żaden sposób 6 ani niczego innego niż 5 przy tych samych danych wejściowych . To jest niemożliwe.
Cytujący autor idzie o krok dalej.
Kontekst został wcześniej zdefiniowany jako „na dowolnym deterministycznym urządzeniu”. Mógłbym zakończyć tę dyskusję tutaj. Ale co, jeśli zmienimy kontekst, wprowadzając nowy element do systemu? Element niedeterministyczny dodany jako dane wejściowe czyni system systemem niedeterministycznym. Jednak poprzez usunięcie elementu niedeterministycznego sprowadzamy się z powrotem do systemu deterministycznego. Jeśli potrafimy w jakiś sposób prześledzić lub w inny sposób odtworzyć dane wejściowe, możemy odtworzyć wynik. Cały ten akapit jest jednak ściśle związany z tym, co mówi autor. Zapamiętaj kontekst.
Można spierać się o znaczenie niedeterminizmu. Jeszcze raz tangetenial. Zapamiętaj kontekst.
Więc ma rację. Na żadnym deterministycznym urządzeniu układ deterministyczny nie może wygenerować prawdziwego losowego wyniku.
źródło