Dlaczego ludzie twierdzą, że występuje błąd modulo podczas korzystania z generatora liczb losowych?

277

Często widziałem to pytanie, ale nigdy nie widziałem na nie konkretnej odpowiedzi. Zamierzam więc zamieścić tutaj jeden, który, mam nadzieję, pomoże ludziom zrozumieć, dlaczego dokładnie występuje „błąd modulo” podczas korzystania z generatora liczb losowych, jak rand()w C ++.

użytkownik1413793
źródło

Odpowiedzi:

394

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_MAXjest to 10 i postanawiam wygenerować losową liczbę od 0 do 2, dzwoniąc rand()%3. Jednak rand()%3nie 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()%nzwraca 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_MAXz 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_MAXszansę na uzyskanie wartości w swoim zakresie, więc musisz wykonywać RAND_MAX/npołą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 nrzadko będzie to wymagało więcej niż jednego połączenia z rand().


Prace cytowane i dalsze czytanie:


użytkownik1413793
źródło
6
Innym sposobem myślenia o RAND_MAX%n == n - 1_ _ jest (RAND_MAX + 1) % n == 0. Czytając kod, rozumiem go % something == 0jako „równomiernie podzielny” łatwiej niż inne sposoby jego obliczania. Oczywiście, jeśli twój stdlib w C ++ ma RAND_MAXtaką samą wartość jak INT_MAX, na (RAND_MAX + 1)pewno nie zadziała; więc obliczenia Marka pozostają najbezpieczniejszą implementacją.
Slipp D. Thompson,
bardzo ładna odpowiedź!
Sayali Sonawane
Być może robię drobne poprawki, ale jeśli celem jest zmniejszenie ilości zmarnowanych bitów, możemy to nieco poprawić w przypadku krawędzi, w której RAND_MAX (RM) jest tylko o 1 mniejszy niż bycie równo podzielnym przez N. W tym scenariuszu nie trzeba marnować żadnych bitów przez robi X> = (RM - RM% N)), która ma małą wartość dla małych wartości N, ale staje się większa dla dużych wartości N. Jak wspomniano przez Slippa D. Thompsona, istnieje rozwiązanie, które będzie działać tylko kiedy INT_MAX (IM)> RAND_MAX, ale pęka, gdy są równe. Istnieje jednak proste rozwiązanie tego problemu, możemy zmienić obliczenia X> = (RM - RM% N) w następujący sposób:
Ben Personick
X> = RM - (((RM% N) + 1)% N)
Ben Personick
Zamieściłem dodatkową odpowiedź, szczegółowo wyjaśniając problem i podając przykładowe rozwiązanie kodu.
Ben Personick
36

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.

// Assumptions
// rand() in [0, RAND_MAX]
// n in (0, RAND_MAX]

int x; 

// Keep searching for an x in a range divisible by n 
do {
    x = rand();
} while (x >= RAND_MAX - (RAND_MAX % n)) 

x %= n;

Powyższa pętla powinna być bardzo szybka, powiedzmy średnio 1 iteracja.

Nick Dandoulakis
źródło
2
Fuj :-P konwersja na podwójną, a następnie pomnożenie przez MAX_UPPER_LIMIT / RAND_MAX jest znacznie czystsze i działa lepiej.
boycy
22
@boycy: nie trafiłeś w sedno. Jeśli liczba wartości, które 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).
TonyK
4
@TonyK przepraszam, nie trafiłem w sedno. Nie zastanawiałem się wystarczająco i pomyślałem, że uprzedzenie będzie miało zastosowanie tylko w przypadku metod wykorzystujących jawną operację modułu. Dzięki za naprawienie mnie :-)
boycy
Pierwszeństwo operatorów sprawia, że RAND_MAX+1 - (RAND_MAX+1) % ndziała poprawnie, ale nadal uważam, że powinno być napisane RAND_MAX+1 - ((RAND_MAX+1) % n)dla jasności.
Linus Arver
4
To nie zadziała, jeśli RAND_MAX == INT_MAX (tak jak w większości systemów) . Zobacz mój drugi komentarz do @ user1413793 powyżej.
BlueRaja - Danny Pflughoeft
19

@ user1413793 ma rację co do problemu. Nie będę o tym dalej dyskutować, z wyjątkiem jednego stwierdzenia: tak, dla małych wartości ni dużych wartości RAND_MAXodchylenie 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 jak arc4random_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_uniformna 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 :

/*
 * Calculate a uniformly distributed random number less than upper_bound
 * avoiding "modulo bias".
 *
 * Uniformity is achieved by generating new random numbers until the one
 * returned is outside the range [0, 2**32 % upper_bound).  This
 * guarantees the selected random number will be inside
 * [2**32 % upper_bound, 2**32) which maps back to [0, upper_bound)
 * after reduction modulo upper_bound.
 */
u_int32_t
arc4random_uniform(u_int32_t upper_bound)
{
    u_int32_t r, min;

    if (upper_bound < 2)
        return 0;

    /* 2**32 % x == (2**32 - x) % x */
    min = -upper_bound % upper_bound;

    /*
     * This could theoretically loop forever but each retry has
     * p > 0.5 (worst case, usually far better) of selecting a
     * number inside the range we need, so it should rarely need
     * to re-roll.
     */
    for (;;) {
        r = arc4random();
        if (r >= min)
            break;
    }

    return r % upper_bound;
}

Warto zwrócić uwagę na najnowszy komentarz dotyczący tego kodu dla tych, którzy muszą zaimplementować podobne rzeczy:

Zmień arc4random_uniform (), aby obliczyć 2**32 % upper_boundjako -upper_bound % upper_bound. Upraszcza kod i czyni go takim samym zarówno w architekturze ILP32, jak i LP64, a także nieco szybciej w architekturach LP64, używając 32-bitowej reszty zamiast 64-bitowej reszty.

Wskazał Jorden Verwer na tech @ ok deraadt; żadnych zastrzeżeń ze strony DJ-a lub Ottona

Implementacja Java jest również łatwa do znalezienia (patrz poprzedni link):

public int nextInt(int n) {
   if (n <= 0)
     throw new IllegalArgumentException("n must be positive");

   if ((n & -n) == n)  // i.e., n is a power of 2
     return (int)((n * (long)next(31)) >> 31);

   int bits, val;
   do {
       bits = next(31);
       val = bits % n;
   } while (bits - val + (n-1) < 0);
   return val;
 }
Rob Napier
źródło
Zauważ, że jeśli 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 implementacji arcfour_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/…
rmalayter
2
@rmalayter Na iOS i OS X arc4random czyta z / dev / random, który jest entropią najwyższej jakości w systemie. (Nazwa „arc4” jest historyczna i zachowana w celu zachowania kompatybilności.)
Rob Napier,
@Rob_Napier warto wiedzieć, ale w /dev/randomprzeszł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).
rmalayter,
1
Jestem zmieszany. Nie jest -upper_bound % upper_bound == 0??
Jon McClung,
1
@JonMcClung -upper_bound % upper_boundrzeczywiście będzie wynosił 0, jeśli intjest szerszy niż 32-bity. Powinno tak być (u_int32_t)-upper_bound % upper_bound)(zakładając, że u_int32_tjest to BSD-ism uint32_t).
Ian Abbott,
14

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:

000 = 0, 001 = 1, 010 = 2, 011 = 3
100 = 4, 101 = 5, 110 = 6, 111 = 7

Możemy zmniejszyć rozmiar zestawu wyników do dokładnie 6, przyjmując wartość modulo 6, jednak przedstawia to problem błędu modulo : 110daje 0, a 111daje 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ść 110i 111i 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ę:

4 discarded results / 16 possibilities = 25%

W tym przypadku 1 dodatkowy bit wcale nie pomógł !

Ten wynik jest niefortunny, ale spróbujmy ponownie z 5 bitami:

32 % 6 = 2 discarded results; and
2 discarded results / 32 possibilities = 6.25%

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:

  1. Jeśli dodamy wystarczającą liczbę bitów, czy istnieje gwarancja, że ​​prawdopodobieństwo odrzucenia zmniejszy się?
  2. Ile bitów wystarczy w ogólnym przypadku?

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,

[2^x mod 6] / 2^x == [2^(x+1) mod 6] / 2^(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.

Bez oferowania dodatkowego dowodu, generalnie użycie podwójnej liczby wymaganych bitów zapewni mniejszą, zwykle nieznaczącą, szansę na odrzucenie.

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 -lcryptoktórej większość powinna być dostępna.

#include <iostream>
#include <assert.h>
#include <limits>
#include <openssl/rand.h>

volatile uint32_t dummy;
uint64_t discardCount;

uint32_t uniformRandomUint32(uint32_t upperBound)
{
    assert(RAND_status() == 1);
    uint64_t discard = (std::numeric_limits<uint64_t>::max() - upperBound) % upperBound;
    uint64_t randomPool = RAND_bytes((uint8_t*)(&randomPool), sizeof(randomPool));

    while(randomPool > (std::numeric_limits<uint64_t>::max() - discard)) {
        RAND_bytes((uint8_t*)(&randomPool), sizeof(randomPool));
        ++discardCount;
    }

    return randomPool % upperBound;
}

int main() {
    discardCount = 0;

    const uint32_t MODULUS = (1ul << 31)-1;
    const uint32_t ROLLS = 10000000;

    for(uint32_t i = 0; i < ROLLS; ++i) {
        dummy = uniformRandomUint32(MODULUS);
    }
    std::cout << "Discard count = " << discardCount << std::endl;
}

Zachęcam do gry z wartościami MODULUSi ROLLS, 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.

Jim Wood
źródło
Naprawdę mam nadzieję, że nikt nie ślepo skopiował twojej jednolitej przypadkowej implementacji. randomPool = RAND_bytes(...)Linia zawsze będzie prowadzić randomPool == 1ze 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 do 1każdej iteracji.
Qix - MONICA MISTREATED
Aby być jasnym, randomPoolzawsze oceni 1zgodnie z dokumentacjąRAND_bytes() OpenSSL, ponieważ zawsze będzie się to udawać dzięki RAND_status()asercji.
Qix - MONICA MISTREATED
9

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

int alea(int n){ 
 assert (0 < n && n <= RAND_MAX); 
 int partSize = 
      n == RAND_MAX ? 1 : 1 + (RAND_MAX-n)/(n+1); 
 int maxUsefull = partSize * n + (partSize-1); 
 int draw; 
 do { 
   draw = rand(); 
 } while (draw > maxUsefull); 
 return draw/partSize; 
}

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 ().

AProgrammer
źródło
n == RAND_MAX? 1: (RAND_MAX-1) / (n + 1): Rozumiem, że tutaj jest pomysł, aby najpierw podzielić RAND_MAX na równy rozmiar strony N, a następnie zwrócić odchylenie w obrębie N, ale nie mogę dokładnie odwzorować kodu na to.
zinking
1
Naiwną wersją powinna być (RAND_MAX + 1) / (n + 1), ponieważ istnieją wartości RAND_MAX + 1 do podzielenia na n + 1 segmentów. Aby uniknąć przepełnienia podczas obliczania RAND_MAX + 1, można go przekształcić w 1+ (RAND_MAX-n) / (n + 1). Aby uniknąć przepełnienia podczas obliczania n + 1, najpierw sprawdza się przypadek n == RAND_MAX.
AProgrammer
+ plus, dzielenie wydaje się kosztować więcej, nawet w porównaniu z liczbami regeneracji.
zinking
4
Biorąc modulo i dzielenie mają te same koszty. Niektóre ISA zapewniają nawet tylko jedną instrukcję, która zawsze zapewnia obie te funkcje. Koszt regeneracji liczb będzie zależeć od n i RAND_MAX. Jeśli n jest małe w stosunku do RAND_MAX, może to kosztować dużo. I oczywiście możesz zdecydować, że uprzedzenia nie są ważne dla twojej aplikacji; Po prostu daję sposób, aby ich uniknąć.
AProgrammer
9

Rozwiązanie Marka (zaakceptowane rozwiązanie) jest prawie idealne.

int x;

do {
    x = rand();
} while (x >= (RAND_MAX - RAND_MAX % n));

x %= n;

zredagowano 25 marca 16 o 23:16

Mark Amery 39k21170211

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(gdzie N= liczba możliwych ważnych wyników).

tzn. gdy „liczba odrzuconych wartości” ( D) jest równa N, to w rzeczywistości są one prawidłowym zestawem (a V)nie niepoprawnym zestawem ( I).

Co powoduje, że w pewnym momencie Mark traci widoczność różnicy między Ni Rand_Max.

Njest zbiorem, którego poprawni członkowie składają się tylko z dodatnich liczb całkowitych, ponieważ zawiera liczbę poprawnych odpowiedzi. (np .: Set N= {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 Maxzbiór wszystkich ważnych wyników, które teoretycznie mogą obejmować liczby ujemne lub wartości nienumeryczne.

Dlatego Rand_Maxjest lepiej zdefiniowany jako zestaw „możliwych odpowiedzi”.

NDziała jednak w stosunku do liczby wartości w zestawie prawidłowych odpowiedzi, więc nawet jak zdefiniowano w naszym konkretnym przypadku, Rand_Maxwartość 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

EG: 

Ran Max Value (RM) = 255
Valid Outcome (N) = 4

When X => 252, Discarded values for X are: 252, 253, 254, 255

So, if Random Value Selected (X) = {252, 253, 254, 255}

Number of discarded Values (I) = RM % N + 1 == N

 IE:

 I = RM % N + 1
 I = 255 % 4 + 1
 I = 3 + 1
 I = 4

   X => ( RM - RM % N )
 255 => (255 - 255 % 4) 
 255 => (255 - 3)
 255 => (252)

 Discard Returns $True

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 .:

D = (RM - N)

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:

RM=255 , N=2 Then: D = 253, Lost percentage = 0.78125%

RM=255 , N=4 Then: D = 251, Lost percentage = 1.5625%
RM=255 , N=8 Then: D = 247, Lost percentage = 3.125%
RM=255 , N=16 Then: D = 239, Lost percentage = 6.25%
RM=255 , N=32 Then: D = 223, Lost percentage = 12.5%
RM=255 , N=64 Then: D = 191, Lost percentage = 25%
RM=255 , N= 128 Then D = 127, Lost percentage = 50%

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:

 int x;

 do {
     x = rand();
 } while (x > (RAND_MAX - ( ( ( RAND_MAX % n ) + 1 ) % n) );

 x %= n;

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:

RAND_MAX = 3, n = 2, Values in RAND_MAX = 0,1,2,3, Valid Sets = 0,1 and 2,3.
When X >= (RAND_MAX - ( RAND_MAX % n ) )
When X >= 2 the value will be discarded, even though the set is valid.

Uogólniona wersja 1:

RAND_MAX = 3, n = 2, Values in RAND_MAX = 0,1,2,3, Valid Sets = 0,1 and 2,3.
When X > (RAND_MAX - ( ( RAND_MAX % n  ) + 1 ) % n )
When X > 3 the value would be discarded, but this is not a vlue in the set RAND_MAX so there will be no discard.

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:

int x;

if n != 0 {
    do {
        x = rand();
    } while (x > (RAND_MAX - ( ( ( RAND_MAX % n ) + 1 ) % n) );

    x %= n;
} else {
    x = rand();
}

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:

// Assumes:
//  RAND_MAX is a globally defined constant, returned from the environment.
//  int n; // User input, or externally defined, number of valid choices.

 int x;

 do {
     x = rand();
 } while (x > (RAND_MAX - ( ( ( RAND_MAX % n ) + 1 ) % n) ) );

 x %= n;

Rozszerzone ogólne rozwiązanie, które umożliwia jeden dodatkowy scenariusz RAND_MAX + 1 = n:

// Assumes:
//  RAND_MAX is a globally defined constant, returned from the environment.
//  int n; // User input, or externally defined, number of valid choices.

int x;

if n != 0 {
    do {
        x = rand();
    } while (x > (RAND_MAX - ( ( ( RAND_MAX % n ) + 1 ) % n) ) );

    x %= n;
} else {
    x = rand();
}

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!

// Assumes:
//  RAND_MAX is a globally defined constant, returned from the environment.
//  int n; // User input, or externally defined, number of valid choices.

int x; // Resulting random number
int y; // One-time calculation of the compare value for x

if n != 0 {
    y = RAND_MAX - ( ( ( RAND_MAX % n ) + 1 ) % n) 
    do {
        x = rand();
    } while (x > y);

    x %= n;
} else {
    x = rand();
}
Ben Personick
źródło
Czy nie jest bezpiecznie powiedzieć, że problem z rozwiązaniem Marka polega na tym, że traktuje RAND_MAX in jako tę samą „jednostkę miary”, podczas gdy w rzeczywistości oznaczają dwie różne rzeczy? Podczas gdy n reprezentuje wynikową „liczbę możliwości”, RAND_MAX reprezentuje tylko maksymalną wartość oryginalnej możliwości, gdzie RAND_MAX + 1 byłby pierwotną liczbą możliwości. Dziwię się, że nie doszedł do twojego wniosku, ponieważ wydawało się, że uznał n, a RAND_MAX to nie to samo z równaniem:RAND_MAX%n = n - 1
Danilo Souza Morães,
@ DaniloSouzaMorães Dziękuję Danilo, przedstawiłeś sprawę bardzo zwięźle. Poszedłem do zademonstrowania, co on robił, wraz z Dlaczego i jak to zrobić, ale nie sądzę, że kiedykolwiek byłem w stanie stwierdzić, CO elokwentnie postępuje źle, ponieważ tak bardzo pochłaniam szczegóły logiki, w jaki sposób i dlaczego istnieje problem, którego nie wyjaśniam tak wyraźnie, o co chodzi. Czy masz coś przeciwko, jeśli zmienię moją odpowiedź, aby wykorzystać część tego, co tu napisałeś, jako moje własne podsumowanie kwestii tego, co i gdzie robi to zaakceptowane rozwiązanie, co należy rozwiązać u góry?
Ben Personick
To byłoby niesamowite. Idź na
całość
1

Przy RAND_MAXwartości 3(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 % 2nie powinieneś robić, jeśli chcesz losową liczbę między 0a 1. Możesz jednak uzyskać losową liczbę między 0i 2wykonując tę % 3czynność, ponieważ w tym przypadku: RAND_MAXjest 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, 0a n - 1więc nróżne możliwości, bez uprzedzeń.

  • liczba bitów (nie bajtów) potrzebnych do zakodowania liczby możliwości to liczba bitów losowych danych, których będziesz potrzebować
  • zakoduj liczbę z losowych bitów
  • jeśli ten numer to >= 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.

next: n

    | bitSize r from to |
    n < 0 ifTrue: [^0 - (self next: 0 - n)].
    n = 0 ifTrue: [^nil].
    n = 1 ifTrue: [^0].
    cache isNil ifTrue: [cache := OrderedCollection new].
    cache size < (self randmax highBit) ifTrue: [
        Security.DSSRandom default next asByteArray do: [ :byte |
            (1 to: 8) do: [ :i |    cache add: (byte bitAt: i)]
        ]
    ].
    r := 0.
    bitSize := n highBit.
    to := cache size.
    from := to - bitSize + 1.
    (from to: to) do: [ :i |
        r := r bitAt: i - from + 1 put: (cache at: i)
    ].
    cache removeFrom: from to: to.
    r >= n ifTrue: [^self next: n].
    ^r
Rivenfall
źródło
-1

Jak wskazuje zaakceptowana odpowiedź , „odchylenie modulo” ma swoje korzenie w niskiej wartości RAND_MAX. Używa bardzo małej wartości RAND_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:

rand() % 3   // if RAND_MAX were only 10, gives
output of rand()   |   rand()%3
0                  |   0
1                  |   1
2                  |   2
3                  |   0
4                  |   1
5                  |   2
6                  |   0
7                  |   1
8                  |   2
9                  |   0

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_MAXjest 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() % 10dla wszystkich celów i celów będzie równomiernie rozłożone, a efekt błędu modulo zniknie.

Bobobobo
źródło
3
Twoja jest bardziej wydajna i prawdopodobnie prawdą jest, że jeśli RAND_MAX jest znacznie większy niż liczba, którą modyfikujesz, jednak twoja nadal będzie stronnicza. To prawda, że ​​i tak są to generatory liczb pseudolosowych i to samo w sobie jest innym tematem, ale jeśli założymy, że generator liczb losowych jest całkowicie losowy, wasza droga wciąż przesądza o niższych wartościach.
user1413793 16.04.13
Ponieważ najwyższa wartość jest nieparzysta, MT::genrand_int32()%2wybiera 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.
bobobobo
7
Pętla jest najlepszym rozwiązaniem. Nie jest to „szalenie nieefektywne”; wymaganie mniej niż dwukrotnej iteracji w najgorszym przeciętnym przypadku. Zastosowanie wysokiej RAND_MAXwartości zmniejszy obciążenie modulo, ale go nie wyeliminuje. Pętla będzie.
Jared Nielsen
5
Jeśli RAND_MAXjest 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, na nie tylko tak, njak sugeruje zaakceptowana odpowiedź.
Mark Ransom,
-3

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 )

int unbiased_random_bit() {    
    int x1, x2, prev;
    prev = 2;
    x1 = rand() % 2;
    x2 = rand() % 2;

    for (;; x1 = rand() % 2, x2 = rand() % 2)
    {
        if (x1 ^ x2)      // 01 -> 1, or 10 -> 0.
        {
            return x2;        
        }
        else if (x1 & x2)
        {
            if (!prev)    // 0011
                return 1;
            else
                prev = 1; // 1111 -> continue, bias unresolved
        }
        else
        {
            if (prev == 1)// 1100
                return 0;
            else          // 0000 -> continue, bias unresolved
                prev = 0;
        }
    }
}
Yavuz Koroglu
źródło
To nie rozwiązuje problemu modulo. Ten proces można wykorzystać do wyeliminowania błędu systematycznego w strumieniu bitów. Jednak przejście ze strumienia bitów do równomiernego rozkładu od 0 do n, gdzie n jest nie mniejsza niż potęga dwóch, wymaga adresowania modulo bias. Zatem to rozwiązanie nie może wyeliminować żadnego błędu w procesie generowania liczb losowych.
Rick,
2
@Rick hmm. Logicznym rozszerzeniem metody von Neumanna na wyeliminowanie błędu modulo przy generowaniu liczby losowej między, powiedzmy, od 1 do 100, byłoby: A) wywołanie rand() % 100100 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.
Mark Amery
@MarkAmery Rzeczywiście powinno to działać. Przeglądając ten algorytm, choć nie jest on poprawnie zaimplementowany. Pierwszym innym powinien być:else if(prev==2) prev= x1; else { if(prev!=x1) return prev; prev=2;}
Rick