Как сгенерировать случайное целое число из диапазона - PullRequest
100 голосов
/ 24 марта 2010

Это продолжение предыдущего вопроса:

Как сгенерировать случайное число в C?

Я хочу иметь возможность генерировать случайное число из определенного диапазона, например, от 1 до 6, чтобы имитировать стороны кристалла.

Как бы я поступил так?

Ответы [ 11 ]

161 голосов
/ 28 июля 2011

Все ответы до сих пор математически неверны. Возвращение rand() % N не дает единообразного числа в диапазоне [0, N), если только N не делит длину интервала, на который возвращается rand() (то есть степень 2). Кроме того, никто не знает, являются ли модули rand() независимыми: возможно, они идут 0, 1, 2, ..., что является равномерным, но не очень случайным. Единственное предположение, которое кажется разумным сделать, состоит в том, что rand() дает распределение Пуассона: любые два непересекающихся подинтервала одинакового размера одинаково вероятны и независимы. Для конечного набора значений это подразумевает равномерное распределение, а также гарантирует, что значения rand() хорошо разбросаны.

Это означает, что единственный правильный способ изменения диапазона rand() - это разделить его на блоки; например, если RAND_MAX == 11 и вы хотите диапазон 1..6, вам следует присвоить {0,1} 1, {2,3} 2 и т. д. Это непересекающиеся интервалы одинакового размера, и поэтому они равномерно и независимо распределены.

Предложение использовать деление с плавающей запятой математически правдоподобно, но в принципе страдает от проблем округления. Возможно, double - достаточно высокая точность, чтобы заставить его работать; возможно нет. Я не знаю, и я не хочу выяснять это; в любом случае ответ зависит от системы.

Правильный способ - использовать целочисленную арифметику. То есть вы хотите что-то вроде следующего:

#include <stdlib.h> // For random(), RAND_MAX

// Assumes 0 <= max <= RAND_MAX
// Returns in the closed interval [0, max]
long random_at_most(long max) {
  unsigned long
    // max <= RAND_MAX < ULONG_MAX, so this is okay.
    num_bins = (unsigned long) max + 1,
    num_rand = (unsigned long) RAND_MAX + 1,
    bin_size = num_rand / num_bins,
    defect   = num_rand % num_bins;

  long x;
  do {
   x = random();
  }
  // This is carefully written not to overflow
  while (num_rand - defect <= (unsigned long)x);

  // Truncated division is intentional
  return x/bin_size;
}

Цикл необходим для получения идеально равномерного распределения. Например, если вам дают случайные числа от 0 до 2, и вы хотите только те от 0 до 1, вы просто продолжаете тянуть, пока не получите 2; нетрудно проверить, что это дает 0 или 1 с равной вероятностью. Этот метод также описан в ссылке, которую nos дал в своем ответе, хотя кодируется по-другому. Я использую random(), а не rand(), поскольку он имеет лучший дистрибутив (как отмечено на справочной странице для rand()).

Если вы хотите получить случайные значения за пределами диапазона по умолчанию [0, RAND_MAX], то вам нужно сделать что-то хитрое. Возможно, наиболее целесообразно определить функцию random_extended(), которая извлекает n бит (используя random_at_most()) и возвращает в [0, 2**n), а затем применяет random_at_most() с random_extended() вместо random()2**n - 1 вместо RAND_MAX), чтобы получить случайное значение меньше 2**n, предполагая, что у вас есть числовой тип, который может содержать такое значение. Наконец, конечно, вы можете получить значения в [min, max], используя min + random_at_most(max - min), включая отрицательные значения.

33 голосов
/ 09 июля 2013

Исходя из ответа @Ryan Reich, я решил предложить свою очищенную версию. Первая проверка границ не требуется, учитывая вторую проверку границ, и я сделал ее итеративной, а не рекурсивной. Возвращает значения в диапазоне [min, max], где max >= min и 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);
}
19 голосов
/ 05 мая 2011

Вот формула, если вам известны максимальные и минимальные значения диапазона и вы хотите сгенерировать числа включительно между диапазонами:

r = (rand() % (max + 1 - min)) + min
17 голосов
/ 24 марта 2010
unsigned int
randr(unsigned int min, unsigned int max)
{
       double scaled = (double)rand()/RAND_MAX;

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

См. здесь для других вариантов.

11 голосов
/ 24 марта 2010

Не могли бы вы просто сделать:

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

% - оператор модуля. По сути, он просто делится на 6 и возвращает остаток ... от 0 до 5

8 голосов
/ 10 июля 2013

Для тех, кто понимает проблему смещения, но не может вынести непредсказуемого времени выполнения методов на основе отклонения, эта серия выдает постепенно уменьшающееся смещение случайное целое число в интервале [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);
...

Это достигается путем синтеза высокоточного случайного числа с фиксированной точкой i * log_2(RAND_MAX + 1) битов (где i - количество итераций) и выполнения длинного умножения на n.

Когда количество битов достаточно велико по сравнению с n, смещение становится неизмеримо малым.

Неважно, если RAND_MAX + 1 меньше n (как в этот вопрос ), или если оно не является степенью двойки, но следует соблюдать осторожность, чтобы избежать целочисленного переполнения, если RAND_MAX * n большой.

4 голосов
/ 05 марта 2016

Чтобы избежать смещения по модулю (предлагается в других ответах), вы всегда можете использовать:

arc4random_uniform(MAX-MIN)+MIN

Где «MAX» - верхняя граница, а «MIN» - нижняя граница. Например, для чисел от 10 до 20:

arc4random_uniform(20-10)+10

arc4random_uniform(10)+10

Простое решение и лучше, чем использование "rand ()% N".

4 голосов
/ 14 мая 2015

Вот немного более простой алгоритм, чем решение Райана Райха:

/// 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
2 голосов
/ 19 октября 2014

Хотя Райан и прав, решение может быть намного проще на основе того, что известно об источнике случайности. Чтобы переформулировать проблему:

  • Существует источник случайности, выводящий целые числа в диапазоне [0, MAX) с равномерным распределением.
  • Цель состоит в том, чтобы получить равномерно распределенные случайные целые числа в диапазоне [rmin, rmax], где 0 <= rmin < rmax < MAX.

По моему опыту, если количество бинов (или "блоков") значительно меньше диапазона исходных чисел, и , исходный источник криптографически силен - нет необходимости проходить через всего этого ригамароле и простого деления по модулю будет достаточно (например, output = rnd.next() % (rmax+1), если rmin == 0), и будут производиться случайные числа, которые распределены равномерно «достаточно» и без потери скорости. Ключевым фактором является источник случайности (то есть дети, не пытайтесь делать это дома с rand()).

Вот пример / доказательство того, как это работает на практике. Я хотел генерировать случайные числа от 1 до 22, имея криптографически сильный источник, который генерировал случайные байты (на основе Intel RDRAND). Результаты:

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%

Это настолько близко к униформе, сколько мне нужно для моих целей (справедливое бросание игральных костей, создание криптографически надежных кодовых книг для шифровальных машин Второй мировой войны, таких как http://users.telenet.be/d.rijmenants/en/kl-7sim.htm, и т. Д.). Вывод не показывает заметного смещения.

Вот источник криптографически сильного (истинного) генератора случайных чисел: Цифровой генератор случайных чисел Intel и пример кода, который генерирует 64-битные (без знака) случайные числа.

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

Я скомпилировал его в Mac OS X с clang-6.0.1 (прямо) и с gcc-4.8.3 с использованием флага "-Wa, q" (потому что GAS не поддерживает эти новые инструкции).

1 голос
/ 17 октября 2013

Как уже говорилось, по модулю недостаточно, потому что это искажает распределение. Вот мой код, который маскирует биты и использует их, чтобы гарантировать, что распределение не искажено.

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

}

Следующий простой код позволяет взглянуть на распределение:

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

}
...