Итак, rand() - это генератор псевдослучайных чисел, который выбирает натуральное число от 0 до RAND_MAX, которое является константой, определенной в cstdlib (см. Это статья для общего обзора rand()).

Что произойдет, если вы захотите сгенерировать случайное число, скажем, от 0 до 2? Для объяснения предположим, что RAND_MAX равно 10, и я решил сгенерировать случайное число от 0 до 2, вызвав rand()%3. Однако rand()%3 не производит числа от 0 до 2 с равной вероятностью!

Когда rand() возвращает 0, 3, 6 или 9, rand()%3 == 0. Следовательно, P (0) = 4/11

Когда rand() возвращает 1, 4, 7 или 10, rand()%3 == 1. Следовательно, P (1) = 4/11

Когда rand() возвращает 2, 5 или 8, rand()%3 == 2. Следовательно, P (2) = 3/11.

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

Итак, когда rand()%n с равной вероятностью возвращает диапазон чисел от 0 до n-1? Когда RAND_MAX%n == n - 1. В этом случае, наряду с нашим предыдущим предположением, rand() действительно возвращает число от 0 до RAND_MAX с равной вероятностью, классы по модулю n также будут равномерно распределены.

Так как же решить эту проблему? Грубый способ - продолжать генерировать случайные числа, пока вы не получите число в желаемом диапазоне:

int x; 
do {
    x = rand();
} while (x >= n);

но это неэффективно для низких значений n, поскольку у вас есть только n/RAND_MAX шанс получить значение в вашем диапазоне, и поэтому вам нужно будет выполнять RAND_MAX/n вызов rand() в среднем.

Более эффективный подход к формуле заключался бы в том, чтобы взять некоторый большой диапазон с длиной, кратной n, например RAND_MAX - RAND_MAX % n, продолжать генерировать случайные числа, пока вы не получите число, лежащее в этом диапазоне, а затем возьмите модуль:

int x;

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

x %= n;

Для небольших значений n это редко требует более одного вызова rand().

Процитированные и дополнительные материалы для чтения:

• Справочник по CPlusPlus

• Вечно запутанный

Постоянный выбор случайного числа - хороший способ устранить предвзятость.

Обновить

Мы могли бы сделать код быстрым, если бы искать x в диапазоне, кратном 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;

Вышеупомянутый цикл должен быть очень быстрым, скажем, в среднем 1 итерация.

@ user1413793 правильно описывает проблему. Я не собираюсь обсуждать это дальше, за исключением одного замечания: да, для малых значений n и больших значений RAND_MAX смещение по модулю может быть очень маленьким. Но использование шаблона, вызывающего смещение, означает, что вы должны учитывать смещение каждый раз, когда вычисляете случайное число и выбираете разные шаблоны для разных случаев. И если вы сделаете неправильный выбор, ошибки, которые он вносит, будут незаметными и практически невозможно протестировать. По сравнению с простым использованием подходящего инструмента (например, arc4random_uniform), это дополнительная работа, а не меньшая работа. Выполнять больше работы и получать худшее решение - это ужасная инженерия, особенно когда делать все правильно каждый раз легко на большинстве платформ.

К сожалению, все реализации решения неверны или менее эффективны, чем должны быть. (У каждого решения есть различные комментарии, объясняющие проблемы, но ни одно из решений не было исправлено для их устранения.) Это может сбить с толку случайного ищущего ответа, поэтому я предлагаю здесь заведомо хорошую реализацию.

Опять же, лучшее решение - просто использовать arc4random_uniform на платформы, которые его предоставляют, или аналогичное решение для вашей платформы (например, _ 5_ на Java). Он будет делать правильные вещи без каких-либо затрат на код. Это почти всегда правильный звонок.

Если у вас нет arc4random_uniform, вы можете использовать возможности открытого исходного кода, чтобы точно увидеть, как он реализован поверх более широкого диапазона ГСЧ (в данном случае ar4random, но аналогичный подход может также работать поверх других ГСЧ) .

Вот реализация 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;
}

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

Измените arc4random_uniform () для вычисления 2**32 % upper_bound как -upper_bound % upper_bound. Упрощает код и делает его одинаковым для архитектур ILP32 и LP64, а также немного быстрее на архитектурах LP64 за счет использования 32-битного остатка вместо 64-битного остатка.

На что указал Джорден Вервер на tech @ ok deraadt; никаких возражений со стороны djm или otto

Реализацию Java также легко найти (см. Предыдущую ссылку):

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

Определение

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

Этого смещения особенно трудно избежать в вычислениях, где числа представлены в виде цепочек битов: нулей и единиц. Найти действительно случайные источники случайности также чрезвычайно сложно, но это выходит за рамки этого обсуждения. В оставшейся части этого ответа предположим, что существует неограниченный источник действительно случайных битов.

Пример проблемы

Давайте рассмотрим моделирование броска кубика (от 0 до 5) с использованием этих случайных битов. Есть 6 возможностей, поэтому нам нужно достаточно битов для представления числа 6, что составляет 3 бита. К сожалению, 3 случайных бита дают 8 возможных результатов:

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

Мы можем уменьшить размер набора результатов ровно до 6, взяв значение по модулю 6, однако это представляет проблему смещения по модулю: 110 дает 0, а 111 дает 1. Этот кубик загружен.

Возможные решения

Подход 0:

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

Подход 1:

Вместо использования модуля наивное, но математически правильное решение - отбросить результаты, которые дают 110 и 111, и просто повторить попытку с 3 новыми битами. К сожалению, это означает, что при каждом броске есть 25% шанс, что потребуется повторный бросок, включая каждый повторный броск. Это явно непрактично для всех случаев, кроме самых тривиальных.

Подход 2:

Используйте больше битов: вместо 3 бит используйте 4. Это дает 16 возможных результатов. Конечно, повторная прокрутка в любое время, когда результат больше 5, ухудшает ситуацию (10/16 = 62,5%), так что это само по себе не поможет.

Обратите внимание, что 2 * 6 = 12 ‹16, поэтому мы можем безопасно взять любой результат меньше 12 и уменьшить его по модулю 6, чтобы равномерно распределить результаты. Остальные 4 исхода должны быть отброшены, а затем повторно выброшены, как и в предыдущем подходе.

Сначала звучит неплохо, но давайте проверим математику:

4 discarded results / 16 possibilities = 25%

В этом случае 1 дополнительный бит не помог!

Результат досадный, но давайте попробуем еще раз с 5 битами:

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

Несомненное улучшение, но во многих практических случаях недостаточно хорошее. Хорошая новость заключается в том, что добавление дополнительных битов никогда не увеличит шансы на необходимость сброса и повторного броска. Это справедливо не только для игральных костей, но и во всех случаях.

Как было продемонстрировано, однако добавление 1 дополнительного бита может ничего не изменить. Фактически, если мы увеличим наш результат до 6 бит, вероятность останется 6,25%.

Это вызывает 2 дополнительных вопроса:

1. Если мы добавим достаточно битов, есть ли гарантия, что вероятность сброса уменьшится?
2. Сколько бит достаточно в общем случае?

Общее решение

К счастью, ответ на первый вопрос - да. Проблема с 6 заключается в том, что 2 ^ x mod 6 переворачивается между 2 и 4, которые по совпадению кратны 2 друг от друга, так что для четного x> 1,

[2^x mod 6] / 2^x == [2^(x+1) mod 6] / 2^(x+1)

Таким образом, 6 - скорее исключение, чем правило. Можно найти более крупные модули, которые дают последовательные степени 2 таким же образом, но в конечном итоге это должно быть циклически повторяться, и вероятность отбрасывания будет уменьшена.

Без дополнительных доказательств, как правило, использование удвоенного количества требуемых битов обеспечивает меньшую, обычно незначительную, вероятность отбрасывания.

Доказательство концепции

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

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

Я рекомендую поиграть со значениями MODULUS и ROLLS, чтобы увидеть, сколько повторов на самом деле происходит в большинстве условий. Скептик может также пожелать сохранить вычисленные значения в файл и убедиться, что распределение выглядит нормальным.

Решение Марка (принятое решение) почти идеально.

int x;

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

x %= n;

Создан 25 мар.

Марк Эмери 39k21170211

Однако у него есть предостережение, которое отбрасывает 1 действительный набор результатов в любом сценарии, где RAND_MAX (RM) на 1 меньше, чем кратное N (где N = количество возможных действительных результатов).

то есть, когда «количество отброшенных значений» (D) равно N, тогда они фактически являются допустимым набором (V), а не недопустимым набором (I).

Причина этого в том, что в какой-то момент Марк упускает из виду разницу между N и Rand_Max.

N - это набор, действительные члены которого состоят только из положительных целых чисел, так как он содержит количество ответов, которые будут действительными. (например: Установить N = {1, 2, 3, ... n })

Rand_max Однако это набор, который (как определено для наших целей) включает любое количество неотрицательных целых чисел.

В наиболее общей форме то, что здесь определяется как Rand Max, представляет собой Набор всех допустимых результатов, которые теоретически могут включать отрицательные числа или нечисловые значения.

Поэтому Rand_Max лучше определить как набор возможных ответов.

Однако N работает с подсчетом значений в наборе действительных ответов, поэтому, даже как определено в нашем конкретном случае, Rand_Max будет значением, на единицу меньшим, чем общее число, которое оно содержит.

Используя решение Марка, значения отбрасываются, когда: 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

Как вы можете видеть в приведенном выше примере, когда значение X (случайное число, которое мы получаем из начальной функции) равно 252, 253, 254 или 255, мы отбрасываем его, даже если эти четыре значения составляют действительный набор возвращаемых значений. .

IE: когда количество отклоненных значений (I) = N (количество допустимых результатов), то исходная функция отбрасывает верный набор возвращаемых значений.

Если мы опишем разницу между значениями N и RM как D, то есть:

D = (RM - N)

Затем, когда значение D становится меньше, процент ненужных повторных бросков из-за этого метода увеличивается при каждом натуральном мультипликативе. (Когда RAND_MAX НЕ равно простому числу, это вызывает серьезную озабоченность)

EG:

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%

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

Чтобы опровергнуть это, мы можем внести простую поправку, как показано здесь:

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

Это обеспечивает более общую версию формулы, которая учитывает дополнительные особенности использования модуля для определения ваших максимальных значений.

Примеры использования небольшого значения для RAND_MAX, которое является мультипликативом N.

Отметить оригинальную версию:

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.

Обобщенная версия 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.

Кроме того, в случае, когда N должно быть количеством значений в RAND_MAX; в этом случае вы можете установить N = RAND_MAX +1, если RAND_MAX = INT_MAX.

По циклу вы можете просто использовать N = 1, и любое значение X будет принято, однако, и вставьте оператор IF для вашего окончательного множителя. Но, возможно, у вас есть код, который может иметь вескую причину для возврата 1, когда функция вызывается с n = 1 ...

Поэтому может быть лучше использовать 0, который обычно дает ошибку Div 0, если вы хотите, чтобы n = RAND_MAX + 1

Обобщенная версия 2:

int x;

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

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

Оба эти решения решают проблему с ненужным отбрасыванием действительных результатов, которые возникают, когда RM + 1 является произведением n.

Вторая версия также охватывает сценарий крайнего случая, когда вам нужно, чтобы n равнялось общему возможному набору значений, содержащемуся в RAND_MAX.

Модифицированный подход в обоих случаях одинаков и позволяет найти более общее решение потребности в предоставлении действительных случайных чисел и минимизации отброшенных значений.

Повторить:

Базовое общее решение, расширяющее пример знака:

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

Расширенное общее решение, допускающее еще один сценарий 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();
}

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

y = RAND_MAX - ( ( ( RAND_MAX % n ) + 1 ) % n) 

if n != 0 {
    do {
        x = rand();
    } while (x > y);

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

Есть две обычные жалобы на использование модуля по модулю.

• один действителен для всех генераторов. Это легче увидеть в предельном случае. Если ваш генератор имеет RAND_MAX, равный 2 (что не соответствует стандарту C), и вы хотите только 0 или 1 в качестве значения, использование modulo будет генерировать 0 в два раза чаще (когда генератор генерирует 0 и 2), чем он будет генерировать 1 (когда генератор генерирует 1). Обратите внимание, что это верно, как только вы не отбрасываете значения, независимо от того, какое отображение вы используете от значений генератора к желаемому, одно будет происходить в два раза чаще, чем другое.

• У какого-то генератора менее значимые биты менее случайны, чем у другого, по крайней мере, для некоторых параметров, но, к сожалению, у этих параметров есть другая интересная характеристика (например, возможность иметь RAND_MAX на единицу меньше степени 2). Проблема хорошо известна, и в течение долгого времени реализация библиотеки, вероятно, избегала проблемы (например, реализация примера rand () в стандарте C использует этот тип генератора, но отбрасывает 16 менее значимых битов), но некоторые любят жаловаться на это и тебе может не повезти

Используя что-то вроде

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

для генерации случайного числа от 0 до n позволит избежать обеих проблем (и избежать переполнения с помощью RAND_MAX == INT_MAX)

Кстати, C ++ 11 представил стандартные способы сокращения и другие генераторы, кроме rand ().

При значении RAND_MAX, равном 3 (на самом деле оно должно быть намного выше, но смещение все равно будет), из этих вычислений следует, что смещение имеет место:

1 % 2 = 1 2 % 2 = 0 3 % 2 = 1 random_between(1, 3) % 2 = more likely a 1

В этом случае % 2 - это то, что вам не следует делать, если вам нужно случайное число от 0 до 1. Вы можете получить случайное число от 0 до 2, выполнив % 3, потому что в этом случае: RAND_MAX кратно 3.

Другой способ

Есть намного проще, но чтобы добавить к другим ответам, вот мое решение для получения случайного числа между 0 и n - 1, поэтому n разные возможности, без предвзятости.

• количество битов (не байтов), необходимых для кодирования количества возможностей - это количество битов случайных данных, которые вам понадобятся
• закодировать число из случайных битов
• если это число >= n, перезапустите (без модуля).

На самом деле случайные данные получить непросто, так зачем использовать больше бит, чем нужно.

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

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

Снижение по модулю - это распространенный способ заставить генератор случайных целых чисел избежать наихудшего случая бесконечной работы.

Однако, когда диапазон возможных целых чисел неизвестен, в целом нет способа исправить этот наихудший случай бесконечного выполнения без внесения смещения. Таким образом, не только уменьшение по модулю (rand() % n, обсуждалось в принятом ответе), но и уменьшение умножения и сдвига Даниэля Лемира, или если вы перестанете отклонять результат после заданного количества итераций. (Для ясности, это не означает, что нет способа исправить проблемы смещения, присутствующие в генераторах псевдослучайных случаев. Например, даже если по модулю и другие сокращения в целом смещены, у них не будет проблем со смещением, если диапазон возможных целые числа - это степень двойки и, если генератор случайных чисел производит несмещенные случайные биты или их блоки.)

Остальная часть этого ответа покажет взаимосвязь между временем работы и смещением в случайных генераторах. С этого момента мы будем предполагать, что у нас есть настоящий генератор случайных чисел, который может производить несмещенные и независимые случайные биты. *

В 1976 году DE Knuth и AC Yao показали, что любой алгоритм, который производит случайные целые числа с заданной вероятностью, используя только случайные биты, может быть представлен в виде двоичного дерева, где случайные биты указывают, каким путем пройти по дереву и каждому листу (конечной точке). соответствует исходу. В этом случае мы имеем дело с алгоритмами, которые генерируют случайные целые числа в [0, n), где каждое целое число выбирается с вероятностью 1 / n. Алгоритм является беспристрастным, если в дереве появляется одинаковое количество листьев для всех результатов. Но если 1 / n имеет неограниченное двоичное раскрытие (что будет иметь место, если n не является степенью 2), алгоритм будет несмещенным, только если:

• двоичное дерево имеет бесконечную глубину, или
• бинарное дерево включает в себя отклоняемые листья на конце,

и в любом случае алгоритм не будет работать в постоянное время, а в худшем случае будет работать вечно. (С другой стороны, когда n является степенью 2, оптимальное двоичное дерево будет иметь конечную глубину и не будет узлов отклонения.)

Концепция двоичного дерева также показывает, что любой способ исправить эту временную сложность наихудшего случая приведет к смещению в целом. (Опять же, это не означает, что нет способа исправить проблемы смещения, присутствующие в псевдослучайных генераторах.) Например, сокращения по модулю эквивалентны двоичному дереву, в котором отклоняемые листья заменяются помеченными результатами, но поскольку существует больше возможных результаты, чем отклонение, только некоторые из результатов могут занять место отклонения, привнося предвзятость. Тот же тип двоичного дерева - и такая же систематическая ошибка - дает результат, если вы перестанете отклонять после заданного количества итераций. (Однако это смещение может быть незначительным в зависимости от приложения. Существуют также аспекты безопасности при генерации случайных целых чисел, которые слишком сложно обсуждать в этом ответе.)

Для иллюстрации следующий код JavaScript реализует алгоритм случайных целых чисел, называемый Fast Dice Roller Дж. Ламброзо ( 2013). Обратите внимание, что он включает в себя событие отклонения и цикл, которые необходимы для обеспечения беспристрастности алгоритма в общем случае.

function randomInt(minInclusive, maxExclusive) {
 var maxInclusive = (maxExclusive - minInclusive) - 1
 var x = 1
 var y = 0
 while(true) {
    x = x * 2
    var randomBit = (Math.random() < 0.5 ? 0 : 1)
    y = y * 2 + randomBit
    if(x > maxInclusive) {
      if (y <= maxInclusive) { return y + minInclusive }
      // Rejection
      x = x - maxInclusive - 1
      y = y - maxInclusive - 1
    }
 }
}

Примечание

* Этот ответ не будет включать функцию rand() в C, потому что он есть много проблем. Возможно, наиболее серьезным здесь является тот факт, что стандарт C явно не определяет конкретное распределение для чисел, возвращаемых rand(), даже не однородное распределение.

Как показывает принятый ответ, «смещение по модулю» имеет свои корни в низком значении RAND_MAX. Он использует чрезвычайно маленькое значение RAND_MAX (10), чтобы показать, что если бы RAND_MAX было 10, то вы попытались сгенерировать число от 0 до 2 с помощью%, результатом были бы следующие результаты:

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

Итак, есть 4 выхода из 0 (шанс 4/10) и только 3 выхода из 1 и 2 (каждый из 3/10 шансов).

Так что это необъективно. У меньших чисел больше шансов выйти.

Но это проявляется так очевидно, только когда RAND_MAX маленький. Или, более конкретно, когда количество, которое вы модифицируете, велико по сравнению с RAND_MAX.

Намного лучшее решение, чем цикл (который безумно неэффективен, и его даже не следует предлагать), - это использовать ГПСЧ с гораздо большим выходным диапазоном. Алгоритм Mersenne Twister имеет максимальный выход 4 294 967 295. Таким образом, выполнение MersenneTwister::genrand_int32() % 10 для всех намерений и целей будет равномерно распределено, и эффект смещения по модулю практически исчезнет.

Я только что написал код для метода беспристрастного подбрасывания монет фон Неймана, который теоретически должен устранить любую систематическую ошибку в процессе генерации случайных чисел. Более подробную информацию можно найти на (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;
        }
    }
}