Jak wygenerować losową liczbę całkowitą z zakresu

Idąc za odpowiedzią @ Ryan Reich, pomyślałem, że zaproponuję moją oczyszczoną wersję. Pierwszy bounds check nie jest wymagany, ponieważ drugi bounds check, i zrobiłem to iteracyjne, a nie rekurencyjne. Zwraca wartości z zakresu [min, max], gdzie max >= min i 1+max-min < RAND_MAX.

unsigned int rand_interval(unsigned int min, unsigned int max)
{
    int r;
    const unsigned int range = 1 + max - min;
    const unsigned int buckets = RAND_MAX / range;
    const unsigned int limit = buckets * range;

    /* Create equal size buckets all in a row, then fire randomly towards
     * the buckets until you land in one of them. All buckets are equally
     * likely. If you land off the end of the line of buckets, try again. */
    do
    {
        r = rand();
    } while (r >= limit);

    return min + (r / buckets);
}

unsigned int
randr(unsigned int min, unsigned int max)
{
       double scaled = (double)rand()/RAND_MAX;

       return (max - min +1)*scaled + min;
}

Zobacz Tutaj dla innych opcji.

Oto wzór, jeśli znasz wartości max i min zakresu i chcesz wygenerować liczby zawierające między zakresem:

r = (rand() % (max + 1 - min)) + min

Wouldn ' t You just do:

srand(time(NULL));
int r = ( rand() % 6 ) + 1;

% jest operatorem modułu. Zasadniczo po prostu podzieli się przez 6 i zwróci resztę... od 0-5

Dla tych, którzy rozumieją problem uprzedzeń, ale nie mogą znieść nieprzewidywalnego czasu trwania metod opartych na odrzuceniu, seria ta wytwarza stopniowo mniej stronniczą losową liczbę całkowitą w przedziale[0, n-1]:

r = n / 2;
r = (rand() * n + r) / (RAND_MAX + 1);
r = (rand() * n + r) / (RAND_MAX + 1);
r = (rand() * n + r) / (RAND_MAX + 1);
...

Robi to poprzez zsyntetyzowanie precyzyjnej liczby losowej i * log_2(RAND_MAX + 1) bitów (gdzie i jest liczbą iteracji) i wykonanie długiego mnożenia przez n.

Gdy liczba bitów jest wystarczająco duża w porównaniu do n, bias staje się niezmiernie mały.

Nie ma znaczenia, czy RAND_MAX + 1 jest mniejsza niż n (jak w to pytanie ), czy nie jest potęgą dwóch, ale należy zachować ostrożność, aby uniknąć przepełnienia liczb całkowitych, Jeśli RAND_MAX * n jest duża.

Aby uniknąć błędu modulo (sugerowanego w innych odpowiedziach), zawsze możesz użyć:

arc4random_uniform(MAX-MIN)+MIN

Gdzie " MAX "to górna granica, A" MIN " to dolna granica. Na przykład dla liczb od 10 do 20:

arc4random_uniform(20-10)+10

arc4random_uniform(10)+10

Proste rozwiązanie i lepsze niż użycie "rand () % N".

Oto nieco prostszy algorytm niż rozwiązanie Ryana Reicha:

/// Begin and end are *inclusive*; => [begin, end]
uint32_t getRandInterval(uint32_t begin, uint32_t end) {
    uint32_t range = (end - begin) + 1;
    uint32_t limit = ((uint64_t)RAND_MAX + 1) - (((uint64_t)RAND_MAX + 1) % range);

    /* Imagine range-sized buckets all in a row, then fire randomly towards
     * the buckets until you land in one of them. All buckets are equally
     * likely. If you land off the end of the line of buckets, try again. */
    uint32_t randVal = rand();
    while (randVal >= limit) randVal = rand();

    /// Return the position you hit in the bucket + begin as random number
    return (randVal % range) + begin;
}

Example (RAND_MAX := 16, begin := 2, end := 7)
    => range := 6  (1 + end - begin)
    => limit := 12 (RAND_MAX + 1) - ((RAND_MAX + 1) % range)

The limit is always a multiple of the range,
so we can split it into range-sized buckets:
    Possible-rand-output: 0  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16
    Buckets:             [0, 1, 2, 3, 4, 5][0, 1, 2, 3, 4, 5][X, X, X, X, X]
    Buckets + begin:     [2, 3, 4, 5, 6, 7][2, 3, 4, 5, 6, 7][X, X, X, X, X]

1st call to rand() => 13
    → 13 is not in the bucket-range anymore (>= limit), while-condition is true
        → retry...
2nd call to rand() => 7
    → 7 is in the bucket-range (< limit), while-condition is false
        → Get the corresponding bucket-value 1 (randVal % range) and add begin
    => 3

Chociaż Ryan ma rację, rozwiązanie może być znacznie prostsze w oparciu o to, co wiadomo o źródle losowości. Aby ponownie określić problem:

• istnieje źródło losowości, wyprowadzające liczby całkowite w zakresie {[2] } z równomiernym rozkładem.
• celem jest uzyskanie równomiernie rozłożonych losowych liczb całkowitych w zakresie [rmin, rmax] Gdzie 0 <= rmin < rmax < MAX.

Z mojego doświadczenia wynika, że jeśli liczba pojemników (lub "pudełek") jest znacznie mniejsza niż zakres liczby pierwotne, i źródło pierwotne jest silne kryptograficznie - Nie ma potrzeby przechodzenia przez cały ten rigamarol, A prosty podział modulo wystarczyłby (jak output = rnd.next() % (rmax+1), Jeśli rmin == 0) i wytworzyłby losowe liczby, które są równomiernie "wystarczająco", bez utraty prędkości. Kluczowym czynnikiem jest źródło losowości (np. dzieci, nie próbujcie tego w domu z rand()).

Oto przykład/dowód na to, jak to działa w praktyce. Chciałem wygenerować losowe liczby od 1 do 22, posiadające silne kryptograficznie źródło, które wytwarzało losowe bajty (oparte na Intel RDRAND). Wyniki są następujące:

Rnd distribution test (22 boxes, numbers of entries in each box):     
 1: 409443    4.55%
 2: 408736    4.54%
 3: 408557    4.54%
 4: 409125    4.55%
 5: 408812    4.54%
 6: 409418    4.55%
 7: 408365    4.54%
 8: 407992    4.53%
 9: 409262    4.55%
10: 408112    4.53%
11: 409995    4.56%
12: 409810    4.55%
13: 409638    4.55%
14: 408905    4.54%
15: 408484    4.54%
16: 408211    4.54%
17: 409773    4.55%
18: 409597    4.55%
19: 409727    4.55%
20: 409062    4.55%
21: 409634    4.55%
22: 409342    4.55%   
total: 100.00%

Jest to tak bliskie jednolitości, jakiej potrzebuję do mojego celu (uczciwy rzut kostką, generowanie silnych kryptograficznie kodeków dla maszyn szyfrujących z II wojny światowej, takich jak http://users.telenet.be/d.rijmenants/en/kl-7sim.htm , itp.). Wyjście nie wykazuje żadnego znaczącego odchylenia.

Oto źródło silnej kryptograficznie (prawdziwej) liczby losowej generator: Intel Digital Random Number Generator]} i przykładowy kod, który tworzy 64-bitowe (niepodpisane) liczby losowe.

int rdrand64_step(unsigned long long int *therand)
{
  unsigned long long int foo;
  int cf_error_status;

  asm("rdrand %%rax; \
        mov $1,%%edx; \
        cmovae %%rax,%%rdx; \
        mov %%edx,%1; \
        mov %%rax, %0;":"=r"(foo),"=r"(cf_error_status)::"%rax","%rdx");
        *therand = foo;
  return cf_error_status;
}

Skompilowałem go na Mac OS X z clang - 6.0.1 (prosto), a z gcc-4.8.3 używając flagi "- Wa, q " (ponieważ GAS nie obsługuje tych nowych instrukcji).

Jak wspomniano wcześniej modulo nie jest wystarczające, ponieważ przekrzywia rozkład. Oto Mój kod, który maskuje bity i używa ich, aby upewnić się, że dystrybucja nie jest wypaczona.

static uint32_t randomInRange(uint32_t a,uint32_t b) {
    uint32_t v;
    uint32_t range;
    uint32_t upper;
    uint32_t lower;
    uint32_t mask;

    if(a == b) {
        return a;
    }

    if(a > b) {
        upper = a;
        lower = b;
    } else {
        upper = b;
        lower = a; 
    }

    range = upper - lower;

    mask = 0;
    //XXX calculate range with log and mask? nah, too lazy :).
    while(1) {
        if(mask >= range) {
            break;
        }
        mask = (mask << 1) | 1;
    }


    while(1) {
        v = rand() & mask;
        if(v <= range) {
            return lower + v;
        }
    }

}

Poniższy prosty kod pozwala spojrzeć na dystrybucję:

int main() {

    unsigned long long int i;


    unsigned int n = 10;
    unsigned int numbers[n];


    for (i = 0; i < n; i++) {
        numbers[i] = 0;
    }

    for (i = 0 ; i < 10000000 ; i++){
        uint32_t rand = random_in_range(0,n - 1);
        if(rand >= n){
            printf("bug: rand out of range %u\n",(unsigned int)rand);
            return 1;
        }
        numbers[rand] += 1;
    }

    for(i = 0; i < n; i++) {
        printf("%u: %u\n",i,numbers[i]);
    }

}