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

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:

• CPlusPlus Odniesienie

• Wiecznie zakłopotany

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.

@ 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;
 }

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.

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

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();
}

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

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.

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;
        }
    }
}