Jak działają generatory liczb losowych?

23

Zastanawiałem się tylko nad rand()funkcją php i zastanawiałem się, jak ją przerobić, i wpadłem całkowicie oszołomiony.

Jak działają generatory liczb losowych?

Korvin Szanto
źródło
2
Generatory liczb pseudolosowych wykorzystują ziarno, tabelę predefiniowanych stałych i formuł matematycznych. Generatory rzeczywistych liczb losowych zwykle wykorzystują hałas atmosferyczny. Możesz łatwo uzyskać losowe liczby z czytania / dev / random.
prawej strony
Czy hałas atmosferyczny jest gwarantowany przypadkowo?
14
function rand() { return 4; /* determined by die roll - guaranteed to be random */ }
Neil
3
Ktoś musi to zrobić: xkcd.com/221 ;)
Valera Kolupaev

Odpowiedzi:

7

Generatory liczb losowych (RNG) naprawdę generują liczby pseudolosowe, ponieważ nie jest możliwe wygenerowanie PRAWDZIWEJ liczby losowej. Jedynymi naprawdę przypadkowymi rzeczami są akty Boga, takie jak błyskawica.

Ten artykuł z Wikipedii może ci pomóc w wyjaśnieniu: http://en.wikipedia.org/wiki/Random_number_generators


Z tego, co rozumiem, są zasadniczo dwie części RNG: ziarno, a następnie losowa liczba wybrana z tego ziarna. Kiedy zasiewasz RNG, dajesz mu równowartość punktu początkowego. W tym punkcie początkowym znajduje się garść liczb, które są „wewnątrz” tego, z którego program wybiera. W PHP możesz użyć srand (), aby „przetasować” nasiona, więc prawie zawsze otrzymasz inną odpowiedź. Następnie możesz użyć rand (min., Maks.), Aby przejść do nasion i wybrać liczbę między min. A maks. Włącznie.


OSTRZEŻENIE, MOŻLIWA ANALOGOWA SERA PONOWNIE!

Pomyśl o każdym „nasieniu” jak o lodowej skrzyni, a następnie o losowych liczbach jak o kostkach lodu. Załóżmy, że masz 1000 skrzyń z lodem, a każda skrzynia ma w środku 1000 kostek lodu. Na targach hrabstwa wybiorą skrzynię z lodem, z której będą mogli się napić, i będą mogli użyć tylko jednej kostki lodu. Potrzebują jednak tylko kostek lodu większych niż 1 cal sześcienny. Więc wybiorą losową skrzynię spośród 1000 skrzyń, a następnie losowo wybiorą kostkę lodu w tej skrzyni. Jeśli to działa na żądany rozmiar, używają go. Jeśli nie, wkładają go z powrotem do skrzyni z innymi. Jeśli chcą sprawić, by było trochę więcej zabawy, najpierw zmieniają skrzynie, aby całkowicie nieświadomość, jeśli chcesz!

Jeśli chodzi o to, jak PHP faktycznie wybiera ziarno i liczbę losową, nie mam na to wystarczającej wiedzy (prawdopodobnie o tym najbardziej się zastanawiałeś!). Nie próbowałbym przerobić funkcji rand (); w większości tworzonych aplikacji internetowych rand () powinien wystarczyć dla dowolnej liczby losowej, której potrzebujesz.

Sprawdź także liniowe generatory kongruencjalne, może to być więcej tego, czego szukasz, jeśli chcesz brudne szczegóły: http://en.wikipedia.org/wiki/Linear_congruential_generator

Mam nadzieję że to pomoże!


źródło
7
W jaki sposób akty godbyłyby przypadkowe w najmniejszym stopniu? Co więcej, błyskawica również nie jest losowa, podąża ścieżką określoną przez różne warunki. Również tłumacz generujący liczbę jest w zasadzie nieistotny.
7
Używam aktów Boga w sensie prawnym: en.wikipedia.org/wiki/Act_of_God Są uważani za przypadkowych, ponieważ są poza oczywistą kontrolą człowieka.
4
Zasadniczo więc nie ma nic losowego. Ale wymagałoby to wpłynięcia na każdą pozornie przypadkową sytuację, która nie działa, gdy dojdziesz do samego początku czasu ... Wygląda na to, że pójdę na zajęcia z filozofii = D
6
@Korvin, o ile wiemy, zjawiska kwantowe, takie jak rozpad promieniotwórczy lub emisja fotonu przez wzbudzony atom, są rzeczywiście przypadkowe. Jednak matematycy i filozofowie spierają się, co to znaczy być naprawdę przypadkowym. I chociaż zwykli ludzie myślą, że rzut monetą jest dość przypadkowy, zwinni magowie sceniczni ( news.stanford.edu/pr/2004/diaconis-69.html ) mogą regularnie zdobywać 10 głów na 10 rzutów.
Charles E. Grant,
1
@Charles - Rzut monetą nie jest nawet dwójką głów / reszek, to w rzeczywistości główki / reszka / krawędź, więc naprawdę dobry mag na scenie może sprawić, że spadnie ani z głów, ani z reszek. * 8 ')
Mark Booth,
18

Zazwyczaj nie są tak naprawdę losowe, ale nazywane są pseudolosowymi, ponieważ generują sekwencję liczb, która wydaje się losowa. Dokonuje się tego za pomocą kilku interesujących wzorów matematycznych. Jednym z najczęstszych jest liniowy generator zbieżny .

Liczby pseudolosowe mają jedną użyteczną właściwość, której nie mają prawdziwe liczby losowe: jeśli użyjesz tego samego ziarna na początku, otrzymasz identyczną sekwencję. Może to być bardzo przydatne do testowania.

Mark Ransom
źródło
Jeśli dobrze rozumiem twoje drugie stwierdzenie: random(5332)zawsze będzie równe random(5332)?
2
@Korvin, nie mam na myśli, że jeśli zadzwonisz, srand(5332)następny numer , który otrzymałeś, randbędzie zawsze taki sam.
Mark Ransom,
3
„wydaje się losowy” -> ma te same właściwości statystyczne, co prawdziwie losowe liczby.
+1 dla linku Wikipedia LGC, to doskonała animacja pokazująca, dlaczego proste PRNG mają poważne ograniczenia podczas wykonywania wielopłaszczyznowych symulacji Monte-Carlo.
Mark Booth,
4

Czy pytasz o Pseudolosowy lub Losowy? Inni odpowiedzieli o pseudolosie, pozwól mi porozmawiać o Randomie.

W sprzedaży były (są?) Rzeczywiste sprzętowe generatory liczb losowych. Oparte były na chipie z małym radiem mierzącym biały szum promieniowania kosmicznego lub małej próbce radioaktywnej i mierzącym okresy między jego rozpadem. Problem z nimi polegał na przepustowości - ilość entropii, którą mogły wygenerować, nie była bardzo wysoka, więc zastosowano je do zarodków algorytmów pseudolosowych. Były używane w systemach bankowych, systemach wysokiego bezpieczeństwa i podobnych.

OTOH, jeśli spotkasz dowolnego programistę systemów wbudowanych, będą się z niego śmiać. Do typowych celów w programowaniu mikrokontrolera, czytanie niskich 4 bitów dowolnego 16-bitowego przetwornika analogowo-cyfrowego za pomocą pływającego (niepodłączonego) pinu będzie generować idealnie dobry losowy szum, przy więcej niż wystarczającej przepustowości (im krótszy okres odpytywania, tym więcej " zaszumiony „odczyt) i łatwiejsze niż pisanie rzeczywistej procedury RNG. Biorąc pod uwagę, że ADC są powszechnie spotykane zaimplementowane w krzemie mikrokontrolerów, często zaimplementowane i często zaimplementowane z 8 kanałami, z których potrzebujesz może 5 do swojej aplikacji, jest to praktycznie darmowe.

I nawet jeśli nie masz ADC, kilka elementów podłączonych do cyfrowego pinu GPIO będzie generować całkiem niezły szum. We wbudowanym szumie są zawsze obecne (i stale zwalczane), więc uzyskanie prawdziwej przypadkowości jest bardzo łatwe.

SF.
źródło
2

Istnieje wiele sposobów naśladowania „losowej” sekwencji liczb. Na pewno pierwszym krokiem powinno być przeczytanie o liniowych generatorach kongruencjalnych . Tak działają najbardziej podstawowe generatory liczb losowych i założę się, że tak działa funkcja rand () PHP.

Bardziej interesujące pytanie, nad którym należy się zastanowić, to w jaki sposób samo się nasia? czas? Adres IP? itp.


źródło
Ziarno mnie dezorientuje, nie mogę wymyślić niczego, co mogłoby zasiać funkcję bez jakiegoś wzorca, a nawet jeśli nie, to co powoduje generowanie losowego nasienia!
3
Uważam, że znacznik czasu jest często używany jako początkowy materiał siewny, gdy tak naprawdę nie jest dostarczany z innego źródła. W starym języku BASIC RANDOMIZE TIMERbył wspólnym idiomem i „wystarczająco dobry” do większości (niekryptograficznych) celów. Według man 3 srand , biblioteka GNU C używa stałej wartości początkowej 1, dopóki PRNG nie zostanie ponownie zasiane.
CVn
1

Po pierwsze, praktycznie wszystkie rand()funkcje nie zapewniają prawdziwej losowości, a raczej zapewniają tak zwane liczby pseudolosowe.

Jak działają generatory liczb pseudolosowych? Zasadniczo w ten sam sposób, w jaki działa szyfrowanie: masz funkcję (skrót), która pobiera dane wejściowe i generuje dane wyjściowe w tak złożony sposób, że nie można zgadnąć danych wejściowych na odwrót. Oznacza to, że każdy szyfr można wykorzystać do stworzenia raczej dobrego generatora pseudolosowego. Jednak chociaż można użyć dowolnego generatora pseudolosowego do szyfrowania, większość generatorów liczb pseudolosowych jest opracowana przede wszystkim z myślą o szybkości, a nie bezpieczeństwie kryptograficznym, więc nie przysporzy hakerów żadnych problemów.

W przypadku generatora pseudolosowego funkcja haszująca jest stosowana do jakiegoś ukrytego wewnętrznego stanu generatora, a jego dane wyjściowe są wykorzystywane do a) modyfikacji tego stanu wewnętrznego ib) do obliczenia wyniku rand()funkcji. Kolejne wywołanie rand()spowoduje użycie tego zmienionego stanu wewnętrznego, a tym samym uzyskanie innego wyniku. Im lepsza funkcja skrótu, tym trudniej odróżnić wyniki od prawdziwych liczb losowych.


W rzeczywistości komputery mają obecnie dostęp do prawdziwych liczb losowych: wynikają one z fluktuacji w czasie przerwań generowanych przez urządzenia zewnętrzne. Linux wykorzystuje te wartości małej niepewności do ciągłego mieszania „puli entropii”, która stanowi zaledwie kilka kilobajtów stanu wewnętrznego. Skrypty kryptograficzne oparte na tej puli entropii są udostępniane za pośrednictwem urządzeń /dev/randomi /dev/urandom. Tak więc dostęp do naprawdę dobrych liczb losowych jest tak prosty, jak otwarcie jednego z tych dwóch urządzeń i odczytanie z nich niektórych bajtów.

cmaster - przywróć monikę
źródło
-2

Liczby losowe to liczby generowane przez proces, którego wynik jest nieprzewidywalny. tzn. nie możemy powiedzieć, co będzie następnym wyjściem. Możemy wziąć prosty przykład wyniku kości. To, co zostanie wydane, gdy rzucimy kostką, jest nieprzewidywalne.

Istnieją dwa rodzaje liczb losowych 1. Prawdziwe liczby losowe 2. Pseudolosowe liczby.

Jak generowane są liczby losowe

Badal
źródło
1
Skorzystaj z formatowania cytatów, aby podkreślić, które części odpowiedzi należą do Ciebie, a które z cytowanego źródła. Jeśli twoja odpowiedź brzmi: kopiuj / wklej z zewnętrznego źródła, nie jest to dobra odpowiedź tutaj.
Mat
wydaje się, że nie oferuje to nic istotnego w porównaniu z punktami przedstawionymi i wyjaśnionymi w poprzednich 6 odpowiedziach
komnata