Однородность случайных чисел, взятых по модулю N

Один общий способ выбора случайного числа в [0, n) - взять результат rand() по модулю n: rand() % n. Однако, даже если результаты, возвращаемые доступной реализацией rand(), полностью однородны, не должно быть проблемы с равномерностью полученных [0, n) чисел, когда RAND_MAX + 1 не делит равномерно на n? Например. предположим, что RAND_MAX равно 2, а n равно 2. Тогда из 3 возможных выходов rand(): 0, 1 и 2 мы получаем 0, 1 и 0 соответственно, когда мы используем их по модулю n. Поэтому выход не будет равномерным.

Это реальная проблема на практике? Каков наилучший способ выбора случайных чисел в [0, n), равномерно получаемых из вывода rand(), предпочтительно без какой-либо арифметики с плавающей запятой?

Ответ 1

Вы правы, rand() % N не точно равномерно распределен. Точно, насколько это важно, зависит от диапазона чисел, которые вы хотите, и от степени случайности, которую вы хотите, но если вы хотите достаточно случайности, что вам даже все равно, вы не хотите использовать rand() в любом случае. Получите настоящий генератор случайных чисел.

Тем не менее, чтобы получить реальное случайное распределение, измените до следующей степени 2 и выборки, пока не получите один из нужного диапазона (например, для 0-9, используйте while(n = rand()%0x10 > 10);).

Ответ 2

Это зависит от:

Значение RAND_MAX
Ваше значение N

Предположим, что ваш RAND_MAX равен 2 ^ 32. Если N довольно мало (скажем 2), то смещение равно 1/2/31 - или слишком мало, чтобы заметить.

Но если N немного больше, скажем 2 ^ 20, то смещение составляет 1/2 ^ 12, или около 1 в 4096 году. Много больше, но все еще довольно мало.

Ответ 3

Один из подходов, который вы можете сделать, это следующее:

Зная значение N, вы делаете R_MAX = ((RAND_MAX + 1) / N) * N; для однородности.

Итак, вы можете выполнить свою собственную функцию rand():

int custom_rand(int mod) {
    int x = rand();
    const int R_MAX = ((RAND_MAX + 1) / mod) * mod;    

    while (x > R_MAX) { // discard the result if it is bigger
        x = rand();
    }

    return (x % mod);
}

Ответ 4

Есть две проблемы с использованием остатка (% не является "модульным" оператором в C) для равномерного случайного числа в приведенном диапазоне. Во-первых, есть небольшое смещение к меньшим числам (упомянутое выше), а во-вторых, что типичные PRNG обычно менее случайны в битах младшего порядка. Я, кажется, помню, что из Knuth ( "Искусство программирования", Vol II, Seminumerical Algorithms) наряду с утверждением, что (после перевода из MIX в C) rand()% 2 является слабым источником случайных одиночных бит. Лучше выбрать (rand() > RAND_MAX/2) (или проверить бит высокого порядка, если RAND_MAX почти равен 2.)

Остальная часть должна быть достаточно хорошей в случайном порядке на небольших промежутках. Избегайте его для моделирования. Собственно, избегайте rand() вообще для больших симуляций или расчетов "Монте-Карло". Реализации имеют период порядка 2 ^ 32 или менее. Нетрудно превысить 4 миллиарда испытаний на процессоре с частотой 2+ ГГц.