Tak więc rand()
jest pseudolosowym generatorem liczb, który wybiera liczbę naturalną od 0 do RAND_MAX
, która jest stałą zdefiniowaną w cstdlib
(zobacz ogólny artykuł na tematrand()
).
Co się stanie, jeśli chcesz wygenerować losową liczbę między powiedzmy 0 a 2? Dla wyjaśnienia, powiedzmy, że RAND_MAX
jest to 10 i postanawiam wygenerować losową liczbę od 0 do 2, dzwoniąc rand()%3
. Jednak rand()%3
nie produkuje liczb od 0 do 2 z jednakowym prawdopodobieństwem!
Gdy rand()
powraca 0, 3, 6 lub 9, rand()%3 == 0
. Dlatego P (0) = 4/11
Kiedy rand()
zwraca 1, 4, 7 lub 10 rand()%3 == 1
,. Dlatego P (1) = 4/11
Kiedy rand()
zwraca 2, 5 lub 8 rand()%3 == 2
,. Dlatego P (2) = 3/11
Nie generuje to liczb od 0 do 2 z jednakowym prawdopodobieństwem. Oczywiście w przypadku małych zakresów może nie być to największy problem, ale w przypadku większego zakresu może to wypaczyć rozkład, powodując przesunięcie mniejszych liczb.
Kiedy więc rand()%n
zwraca zakres liczb od 0 do n-1 z jednakowym prawdopodobieństwem? Kiedy RAND_MAX%n == n - 1
. W tym przypadku, wraz z naszym wcześniejszym założeniem rand()
, zwraca liczbę między 0 i RAND_MAX
z jednakowym prawdopodobieństwem, klasy modulo n również byłyby równomiernie rozłożone.
Jak więc rozwiązać ten problem? Prostym sposobem jest generowanie liczb losowych, dopóki nie otrzymasz liczby w żądanym zakresie:
int x;
do {
x = rand();
} while (x >= n);
ale jest to nieefektywne w przypadku niskich wartości n
, ponieważ masz tylko n/RAND_MAX
szansę na uzyskanie wartości w swoim zakresie, więc musisz wykonywać RAND_MAX/n
połączenia zrand()
średnio.
Bardziej wydajnym podejściem do formuły byłoby przyjęcie pewnego dużego zakresu o długości podzielnej przez n
, na przykład RAND_MAX - RAND_MAX % n
, generowanie liczb losowych, dopóki nie otrzymasz liczby, która leży w zakresie, a następnie weź moduł:
int x;
do {
x = rand();
} while (x >= (RAND_MAX - RAND_MAX % n));
x %= n;
W przypadku małych wartości n
rzadko będzie to wymagało więcej niż jednego połączenia z rand()
.
Prace cytowane i dalsze czytanie:
RAND_MAX%n == n - 1
_ _ jest(RAND_MAX + 1) % n == 0
. Czytając kod, rozumiem go% something == 0
jako „równomiernie podzielny” łatwiej niż inne sposoby jego obliczania. Oczywiście, jeśli twój stdlib w C ++ maRAND_MAX
taką samą wartość jakINT_MAX
, na(RAND_MAX + 1)
pewno nie zadziała; więc obliczenia Marka pozostają najbezpieczniejszą implementacją.Ciągłe wybieranie losowego jest dobrym sposobem na usunięcie błędu.
Aktualizacja
Możemy sprawić, że kod będzie szybki, jeśli szukamy dzielnego zakresu x przez
n
.Powyższa pętla powinna być bardzo szybka, powiedzmy średnio 1 iteracja.
źródło
rand()
można zwrócić, nie jest wielokrotnościąn
, to cokolwiek zrobisz, nieuchronnie otrzymasz „modulo stronniczość”, chyba że odrzucisz niektóre z tych wartości. user1413793 wyjaśnia to ładnie (chociaż rozwiązanie zaproponowane w tej odpowiedzi jest naprawdę trafne).RAND_MAX+1 - (RAND_MAX+1) % n
działa poprawnie, ale nadal uważam, że powinno być napisaneRAND_MAX+1 - ((RAND_MAX+1) % n)
dla jasności.RAND_MAX == INT_MAX
(tak jak w większości systemów) . Zobacz mój drugi komentarz do @ user1413793 powyżej.@ user1413793 ma rację co do problemu. Nie będę o tym dalej dyskutować, z wyjątkiem jednego stwierdzenia: tak, dla małych wartości
n
i dużych wartościRAND_MAX
odchylenie modulo może być bardzo małe. Ale użycie wzorca indukującego błąd systematyczny oznacza, że należy rozważyć błąd systematyczny za każdym razem, gdy obliczasz liczbę losową i wybierasz różne wzory dla różnych przypadków. A jeśli dokonasz złego wyboru, wprowadzone przez niego błędy są subtelne i prawie niemożliwe do przetestowania jednostkowego. W porównaniu do zwykłego użycia odpowiedniego narzędzia (takiego jakarc4random_uniform
), to dodatkowa praca, nie mniej pracy. Wykonywanie większej ilości pracy i uzyskiwanie gorszych rozwiązań jest okropną inżynierią, szczególnie gdy poprawne wykonanie zadania za każdym razem jest łatwe na większości platform.Niestety implementacje rozwiązania są niepoprawne lub mniej wydajne niż powinny. (Każde rozwiązanie ma różne komentarze wyjaśniające problemy, ale żadne z nich nie zostało naprawione, aby je rozwiązać.) Prawdopodobnie wprowadzi to w błąd przypadkowego poszukiwacza odpowiedzi, więc zapewniam tutaj znaną dobrą implementację.
Ponownie najlepszym rozwiązaniem jest po prostu użycie
arc4random_uniform
na platformach, które to zapewniają, lub podobnych rozwiązaniach dystansowych dla Twojej platformy (takich jakRandom.nextInt
Java). Zrobi to dobrze bez żadnego kodu. Prawie zawsze jest to prawidłowe połączenie.Jeśli nie masz
arc4random_uniform
, możesz użyć mocy opensource, aby zobaczyć dokładnie, jak jest ona implementowana na szczycie RNG o szerszym zakresie (ar4random
w tym przypadku, ale podobne podejście może również działać na innych RNG).Oto implementacja OpenBSD :
Warto zwrócić uwagę na najnowszy komentarz dotyczący tego kodu dla tych, którzy muszą zaimplementować podobne rzeczy:
Implementacja Java jest również łatwa do znalezienia (patrz poprzedni link):
źródło
arcfour_random()
faktycznie użyje prawdziwego algorytmu RC4 w swojej implementacji, wynik na pewno będzie miał pewne odchylenie. Mamy nadzieję, że autorzy bibliotek przerzucili się na lepsze CSPRNG za tym samym interfejsem. Przypominam sobie, że jeden z BSD faktycznie wykorzystuje algorytm ChaCha20 do implementacjiarcfour_random()
. Więcej informacji na temat błędów wyjściowych RC4, które czynią go bezużytecznym dla bezpieczeństwa lub innych krytycznych aplikacji, takich jak poker wideo: blog.cryptographyengineering.com/2013/03/…/dev/random
przeszłości używał również RC4 na niektórych platformach (Linux używa SHA-1 w trybie licznika). Niestety strony podręcznika znalezione podczas wyszukiwania wskazują, że RC4 jest nadal używany na różnych platformach, które oferująarc4random
(chociaż rzeczywisty kod może być inny).-upper_bound % upper_bound == 0
??-upper_bound % upper_bound
rzeczywiście będzie wynosił 0, jeśliint
jest szerszy niż 32-bity. Powinno tak być(u_int32_t)-upper_bound % upper_bound)
(zakładając, żeu_int32_t
jest to BSD-ismuint32_t
).Definicja
Modulo BiasOdchylenie jest nieodłącznym odchyleniem przy użyciu arytmetyki modulo w celu zmniejszenia zestawu wyjściowego do podzbioru zestawu wejściowego. Ogólnie rzecz biorąc, odchylenie występuje, ilekroć odwzorowanie między zestawem wejściowym i wyjściowym nie jest równomiernie rozłożone, jak w przypadku zastosowania arytmetyki modulo, gdy wielkość zestawu wyjściowego nie jest dzielnikiem wielkości zestawu wejściowego.
Tego obciążenia jest szczególnie trudne do uniknięcia w obliczeniach, gdzie liczby są reprezentowane jako ciąg bitów: 0 i 1. Znalezienie prawdziwie losowych źródeł losowości jest również niezwykle trudne, ale wykracza poza zakres tej dyskusji. W pozostałej części tej odpowiedzi załóż, że istnieje nieograniczone źródło naprawdę losowych bitów.
Przykład problemu
Rozważmy symulację rzutu kostką (od 0 do 5) przy użyciu tych losowych bitów. Istnieje 6 możliwości, więc potrzebujemy wystarczającej liczby bitów do przedstawienia liczby 6, czyli 3 bitów. Niestety 3 losowe bity dają 8 możliwych wyników:
Możemy zmniejszyć rozmiar zestawu wyników do dokładnie 6, przyjmując wartość modulo 6, jednak przedstawia to problem błędu modulo :
110
daje 0, a111
daje 1. Ta matryca jest obciążona.Potencjalne rozwiązania
Podejście 0:
Zamiast polegać na losowych bitach, teoretycznie można zatrudnić małą armię, aby rzucać kostkami przez cały dzień i zapisywać wyniki w bazie danych, a następnie używać każdego wyniku tylko raz. Jest to tak praktyczne, jak się wydaje, i bardziej niż prawdopodobne, i tak nie przyniosłoby naprawdę przypadkowych wyników (zamierzona gra słów).
Podejście 1:
Zamiast stosowania modułu, naiwne ale matematycznie odpowiednim rozwiązaniem jest odrzucenie wyników, wydajność
110
i111
i prosto spróbować 3 nowe bitów. Niestety oznacza to, że przy każdym rzucie istnieje 25% szansy na to, że wymagany będzie ponowny rzut, w tym każdy z nich sam. Jest to wyraźnie niepraktyczne dla wszystkich zastosowań poza najbardziej trywialnymi.Podejście 2:
Użyj więcej bitów: zamiast 3 bitów, użyj 4. To daje 16 możliwych wyników. Oczywiście ponowne rzutowanie w dowolnym momencie, gdy wynik jest większy niż 5, pogarsza sytuację (10/16 = 62,5%), więc samo to nie pomoże.
Zauważ, że 2 * 6 = 12 <16, więc możemy bezpiecznie wziąć dowolny wynik mniejszy niż 12 i zmniejszyć ten moduł 6, aby równomiernie rozłożyć wyniki. Pozostałe 4 wyniki należy odrzucić, a następnie przerzucić ponownie, jak w poprzednim podejściu.
Na początku brzmi dobrze, ale sprawdźmy matematykę:
Ten wynik jest niefortunny, ale spróbujmy ponownie z 5 bitami:
Zdecydowana poprawa, ale niewystarczająca w wielu praktycznych przypadkach. Dobrą wiadomością jest to, że dodanie większej liczby bitów nigdy nie zwiększy szans na konieczność odrzucenia i ponownego rzutu . Dotyczy to nie tylko kości, ale we wszystkich przypadkach.
Jak jednak wykazano , dodanie 1 dodatkowego bitu nic nie może zmienić. W rzeczywistości, jeśli zwiększymy nasz rzut do 6 bitów, prawdopodobieństwo pozostanie 6,25%.
To pociąga za sobą 2 dodatkowe pytania:
Ogólne rozwiązanie
Na szczęście odpowiedź na pierwsze pytanie brzmi „tak”. Problem z 6 polega na tym, że 2 ^ x mod 6 przerzuca między 2 a 4, które przypadkowo są wielokrotnością 2 od siebie, tak że dla parzystego x> 1,
Zatem 6 jest wyjątkiem, a nie regułą. Możliwe jest znalezienie większych modułów, które dają kolejne moce 2 w ten sam sposób, ale ostatecznie to musi się owijać, a prawdopodobieństwo odrzucenia zostanie zmniejszone.
Dowód koncepcji
Oto przykładowy program, który wykorzystuje libcrypo OpenSSL do dostarczania losowych bajtów. Podczas kompilacji pamiętaj o utworzeniu łącza do biblioteki, w
-lcrypto
której większość powinna być dostępna.Zachęcam do gry z wartościami
MODULUS
iROLLS
, aby zobaczyć, ile przerzutów faktycznie ma miejsce w większości warunków. Sceptyczny człowiek może również chcieć zapisać obliczone wartości do pliku i sprawdzić, czy rozkład wydaje się normalny.źródło
randomPool = RAND_bytes(...)
Linia zawsze będzie prowadzićrandomPool == 1
ze względu na twierdzenia. To zawsze skutkuje odrzuceniem i ponownym rzutem. Myślę, że chciałeś zadeklarować na osobnej linii. W konsekwencji spowodowało to powrót RNG do1
każdej iteracji.randomPool
zawsze oceni1
zgodnie z dokumentacjąRAND_bytes()
OpenSSL, ponieważ zawsze będzie się to udawać dziękiRAND_status()
asercji.Istnieją dwie zwykłe skargi związane z użyciem modulo.
jeden jest ważny dla wszystkich generatorów. Łatwiej jest zobaczyć w przypadku limitu. Jeśli twój generator ma RAND_MAX, który wynosi 2 (co nie jest zgodne ze standardem C) i chcesz tylko 0 lub 1 jako wartość, użycie modulo wygeneruje 0 dwa razy częściej (gdy generator wygeneruje 0 i 2), jak to będzie wygeneruj 1 (gdy generator wygeneruje 1). Zauważ, że jest to prawdą, gdy tylko nie upuścisz wartości, bez względu na to, jakiego mapowania używasz z wartości generatora na poszukiwany, jedno wystąpi dwa razy częściej niż drugie.
jakiś rodzaj generatora ma mniej znaczące bity mniej losowe niż drugi, przynajmniej dla niektórych swoich parametrów, ale niestety te parametry mają inną interesującą cechę (taka jest w stanie mieć RAND_MAX jeden mniejszy niż 2). Problem jest dobrze znany i przez długi czas implementacja biblioteki prawdopodobnie uniknęła problemu (na przykład implementacja rand () w standardzie C używa tego rodzaju generatora, ale upuszcza 16 mniej znaczących bitów), ale niektórzy lubią narzekać i możesz mieć pecha
Używanie czegoś podobnego
wygenerowanie liczby losowej od 0 do n pozwoli uniknąć obu problemów (i pozwoli uniknąć przepełnienia RAND_MAX == INT_MAX)
BTW, C ++ 11 wprowadził standardowe metody redukcji i inne generatory niż rand ().
źródło
Rozwiązanie Marka (zaakceptowane rozwiązanie) jest prawie idealne.
Ma jednak zastrzeżenie, które odrzuca 1 prawidłowy zestaw wyników w każdym scenariuszu, w którym
RAND_MAX
(RM
) jest o 1 mniejszy niż wielokrotnośćN
(gdzieN
= liczba możliwych ważnych wyników).tzn. gdy „liczba odrzuconych wartości” (
D
) jest równaN
, to w rzeczywistości są one prawidłowym zestawem (aV)
nie niepoprawnym zestawem (I
).Co powoduje, że w pewnym momencie Mark traci widoczność różnicy między
N
iRand_Max
.N
jest zbiorem, którego poprawni członkowie składają się tylko z dodatnich liczb całkowitych, ponieważ zawiera liczbę poprawnych odpowiedzi. (np .: SetN
={1, 2, 3, ... n }
)Rand_max
Jest to jednak zestaw, który (jak zdefiniowano dla naszych celów) zawiera dowolną liczbę liczb całkowitych nieujemnych.W najogólniejszej formie zdefiniowano tu
Rand Max
zbiór wszystkich ważnych wyników, które teoretycznie mogą obejmować liczby ujemne lub wartości nienumeryczne.Dlatego
Rand_Max
jest lepiej zdefiniowany jako zestaw „możliwych odpowiedzi”.N
Działa jednak w stosunku do liczby wartości w zestawie prawidłowych odpowiedzi, więc nawet jak zdefiniowano w naszym konkretnym przypadku,Rand_Max
wartość będzie o jeden mniejsza niż całkowita liczba, którą zawiera.Korzystając z rozwiązania Marka, wartości są odrzucane, gdy: X => RM - RM% N
Jak widać w powyższym przykładzie, gdy wartość X (liczba losowa, którą otrzymujemy z funkcji początkowej) wynosi 252, 253, 254 lub 255, odrzucilibyśmy ją, mimo że te cztery wartości zawierają prawidłowy zestaw zwracanych wartości .
IE: Gdy liczba wartości odrzuconych (I) = N (liczba prawidłowych wyników), wówczas prawidłowy zestaw wartości zwracanych zostanie odrzucony przez funkcję oryginalną.
Jeśli opisamy różnicę między wartościami N i RM jako D, tj .:
Następnie, gdy wartość D staje się mniejsza, procent niepotrzebnych przerzutów z powodu tej metody wzrasta przy każdym naturalnym mnożeniu. (Gdy RAND_MAX NIE jest równe liczbie pierwszej, jest to ważne)
NA PRZYKŁAD:
Ponieważ procent potrzebnej liczby ponownych zapytań wzrasta, im bliżej N dochodzi do RM, może to mieć znaczenie przy wielu różnych wartościach, w zależności od ograniczeń systemu z uruchomionym kodem i poszukiwanych wartości.
Aby temu zaradzić, możemy wprowadzić prostą poprawkę Jak pokazano tutaj:
Zapewnia to bardziej ogólną wersję formuły, która uwzględnia dodatkowe osobliwości związane z używaniem modułu do definiowania maksymalnych wartości.
Przykłady użycia małej wartości dla RAND_MAX, która jest wielokrotnością N.
Oryginalna wersja Marka:
Uogólniona wersja 1:
Dodatkowo w przypadku, gdy N powinna być liczbą wartości w RAND_MAX; w takim przypadku możesz ustawić N = RAND_MAX +1, chyba że RAND_MAX = INT_MAX.
Jeśli chodzi o pętle, możesz po prostu użyć N = 1, a każda wartość X zostanie jednak zaakceptowana i umieścisz instrukcję IF w swoim ostatecznym mnożniku. Ale może masz kod, który może mieć prawidłowy powód zwrócenia 1, gdy funkcja jest wywoływana z n = 1 ...
Dlatego może być lepiej użyć 0, które normalnie zapewnia błąd Div 0, jeśli chcesz mieć n = RAND_MAX + 1
Uogólniona wersja 2:
Oba te rozwiązania rozwiązują problem, niepotrzebnie odrzucając prawidłowe wyniki, które pojawią się, gdy RM + 1 będzie iloczynem n.
Druga wersja obejmuje również scenariusz przypadków skrajnych, gdy potrzebujesz n, aby zrównoważyć całkowity możliwy zestaw wartości zawartych w RAND_MAX.
Zmodyfikowane podejście w obu przypadkach jest takie samo i pozwala na bardziej ogólne rozwiązanie potrzeby zapewnienia prawidłowych liczb losowych i minimalizacji odrzuconych wartości.
Powtarzać:
Podstawowe ogólne rozwiązanie rozszerzające przykład znaku:
Rozszerzone ogólne rozwiązanie, które umożliwia jeden dodatkowy scenariusz RAND_MAX + 1 = n:
W niektórych językach (szczególnie językach interpretowanych) wykonywanie obliczeń operacji porównania poza czasem while może prowadzić do szybszych wyników, ponieważ jest to obliczenie jednorazowe, bez względu na to, ile ponownych prób jest wymaganych. YMMV!
źródło
RAND_MAX%n = n - 1
Przy
RAND_MAX
wartości3
(w rzeczywistości powinna być znacznie wyższa, ale uprzedzenie nadal istniałoby), z tych obliczeń ma sens, że istnieje uprzedzenie:1 % 2 = 1
2 % 2 = 0
3 % 2 = 1
random_between(1, 3) % 2 = more likely a 1
W takim przypadku
% 2
nie powinieneś robić, jeśli chcesz losową liczbę między0
a1
. Możesz jednak uzyskać losową liczbę między0
i2
wykonując tę% 3
czynność, ponieważ w tym przypadku:RAND_MAX
jest wielokrotnością3
.Inna metoda
Jest o wiele prostsze, ale aby dodać do innych odpowiedzi, oto moje rozwiązanie, aby uzyskać losową liczbę między,
0
an - 1
więcn
różne możliwości, bez uprzedzeń.>= n
, uruchom ponownie (bez modulo).Naprawdę losowe dane nie są łatwe do uzyskania, więc po co używać większej liczby bitów niż to konieczne.
Poniżej znajduje się przykład w Smalltalk, wykorzystujący pamięć podręczną bitów z generatora liczb pseudolosowych. Nie jestem ekspertem od bezpieczeństwa, więc używaj na własne ryzyko.
źródło
Jak wskazuje zaakceptowana odpowiedź , „odchylenie modulo” ma swoje korzenie w niskiej wartości
RAND_MAX
. Używa bardzo małej wartościRAND_MAX
(10), aby pokazać, że jeśli RAND_MAX wynosi 10, to próbujesz wygenerować liczbę od 0 do 2 za pomocą%, to następują następujące wyniki:Są więc 4 wyjścia zer (szansa 4/10) i tylko 3 wyjścia 1 i 2 (każda szansa 3/10).
To jest stronnicze. Niższe liczby mają większą szansę na wyjście.
Ale to pokazuje się tak wyraźnie, gdy
RAND_MAX
jest małe . A dokładniej, gdy liczba, którą modyfikujesz, jest duża w porównaniu doRAND_MAX
.O wiele lepszym rozwiązaniem niż zapętlenie (które jest niesamowicie nieefektywne i nie powinno być nawet sugerowane) jest użycie PRNG o znacznie większym zakresie wyjściowym. Twister Mersenne algorytm ma maksymalną moc 4294967295. W ten sposób działanie
MersenneTwister::genrand_int32() % 10
dla wszystkich celów i celów będzie równomiernie rozłożone, a efekt błędu modulo zniknie.źródło
MT::genrand_int32()%2
wybiera 0 (50 + 2,3e-8)% czasu i 1 (50 - 2,3e-8)% czasu. O ile nie budujesz RGN kasyna (do którego prawdopodobnie użyłbyś RGN o znacznie większym zakresie), żaden użytkownik nie zauważy dodatkowych 2,3e-8% czasu. Mówisz o liczbach zbyt małych, by mogły mieć znaczenie.RAND_MAX
wartości zmniejszy obciążenie modulo, ale go nie wyeliminuje. Pętla będzie.RAND_MAX
jest wystarczająco większy niż liczba, którą modyfikujesz, liczba powtórzeń losowej liczby jest znikoma i nie wpływa na wydajność. Mówię: kontynuuj zapętlanie, dopóki testujesz na największej wielokrotności,n
a nie tylko tak,n
jak sugeruje zaakceptowana odpowiedź.Właśnie napisałem kod dla Bezstronnej Metody Odrzucania Monet Von Neumanna, która teoretycznie powinna wyeliminować jakiekolwiek odchylenie w procesie generowania liczb losowych. Więcej informacji można znaleźć na stronie ( http://en.wikipedia.org/wiki/Fair_coin )
źródło
rand() % 100
100 razy. B) jeśli wszystkie wyniki są różne, weź pierwszy. C) w przeciwnym razie GOTO A. To zadziała, ale przy oczekiwanej liczbie iteracji około 10 ^ 42 będziesz musiał być dość cierpliwy. I nieśmiertelny.else if(prev==2) prev= x1; else { if(prev!=x1) return prev; prev=2;}