Почему люди говорят, что при использовании генератора случайных чисел наблюдается смещение по модулю?
Я видел, как этот вопрос задавался много, но никогда не видел истинного конкретного ответа на него. Итак, я собираюсь опубликовать один здесь, который, надеюсь, поможет людям понять, почему именно происходит "смещение по модулю" при использовании генератора случайных чисел, например rand() в C++.
11 ответов
Так 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(),
Работы цитируются и читаем дальше:
Продолжайте выбирать случайное число - это хороший способ убрать смещение.
Обновить
Мы могли бы сделать код быстрым, если бы мы искали 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 на платформах, которые предоставляют его, или аналогичное решение для вашей платформы (например, Random.nextInt на 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'' as-upper_bound % upper_bound''. Упрощает код и делает его одинаковым на архитектурах ILP32 и LP64, а также немного быстрее на архитектурах LP64, используя 32-разрядный остаток вместо 64-разрядного остатка.Указано Джорденом Вервером на tech@ ok deraadt; нет возражений от диджей или отто
Реализация 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 и 1. Найти действительно случайные источники случайности также чрезвычайно сложно, но это выходит за рамки этого обсуждения. В оставшейся части этого ответа предположим, что существует неограниченный источник действительно случайных битов.
Пример задачи
Давайте рассмотрим моделирование броска кубика (от 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 дополнительных вопроса:
- Если мы добавим достаточно битов, есть ли гарантия, что вероятность сброса уменьшится?
- Сколько бит достаточно в общем случае?
Общее решение
К счастью, ответ на первый вопрос - да. Проблема с 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 таким же образом, но в конечном итоге это должно обернуться, и вероятность сброса будет уменьшена.
Без дополнительных доказательств, в общем случае использование двойного количества требуемых битов обеспечит меньшую, обычно незначительную, вероятность сброса.
Доказательство концепции
Вот пример программы, которая использует libcrypo для OpenSSL для предоставления случайных байтов. При компиляции обязательно указывайте ссылку на библиотеку с помощью -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 марта 16 в 23:16
Марк Амери 39к21170211
Тем не менее, он имеет оговорку, которая отбрасывает 1 действительный набор результатов в любом сценарии, где RAND_MAX (RM) на 1 меньше, чем кратное N (где N = количество возможных действительных результатов).
т.е. когда "количество отброшенных значений" (D) равно N, тогда они фактически являются действительным набором (V), а не недействительным набором (I).
Используя решение Марка, значения отбрасываются, когда: 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: когда подсчет значений Discarded (I) = N (Количество действительных результатов), то Действительный набор возвращаемых значений будет отброшен исходной функцией.
Если мы опишем разницу между значениями N и RM как D, то есть:
D = (RM - N)
Затем, когда значение D становится меньше, Процент ненужных повторных бросков из-за этого метода увеличивается при каждом естественном мультипликате. (Когда RAND_MAX НЕ равен простому числу, это имеет значение)
НАПРИМЕР:
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%
Поскольку процент необходимых Rerolls увеличивается по мере приближения N к RM, это может иметь значение для многих различных значений в зависимости от ограничений системы, в которой он работает, и от искомых значений.
Чтобы отрицать это, мы можем внести простую поправку, как показано здесь:
int x;
do {
x = rand();
} while (x > (RAND_MAX - ( ( ( RAND_MAX % n ) + 1 ) % n) );
x %= n;
Это обеспечивает более общую версию формулы, которая учитывает дополнительные особенности использования модуля для определения ваших максимальных значений.
Примеры использования небольшого значения для RAND_MAX, который является мультипликативным для N.
Mark'original Версия:
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.
Модифицированный подход в обоих случаях одинаков и позволяет найти более общее решение необходимости предоставления действительных случайных чисел и минимизации отброшенных значений.
Повторить:
Основное общее решение, которое расширяет пример знака:
int x;
do {
x = rand();
} while (x > (RAND_MAX - ( ( ( RAND_MAX % n ) + 1 ) % n) );
x %= n;
Расширенное общее решение, которое допускает один дополнительный сценарий RAND_MAX+1 = n:
int x;
if n != 0 {
do {
x = rand();
} while (x > (RAND_MAX - ( ( ( RAND_MAX % n ) + 1 ) % n) );
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 = 12 % 2 = 03 % 2 = 1random_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 реализует алгоритм случайных целых чисел, названный Дж. Ламброзо (2013) Fast Dice Roller. Обратите внимание, что он включает в себя событие отклонения и цикл, которые необходимы для обеспечения беспристрастности алгоритма в общем случае.
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().
Мне очень нужны случайные дубли с различным программным обеспечением. Я нахожу диапазон более «случайным», если использую ((double)rand()/RAND_MAX). Я предполагаю, что если вы умножите это на свой диапазон чисел, вы сможете получить случайное число с меньшим смещением?
т.е. ((double)rand()/RAND_MAX) * 3.
Я прочитал ответ о том, как получить случайное число из 2. isodd(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,
Гораздо лучшим решением, чем зацикливание (которое безумно неэффективно и даже не следует предлагать), является использование PRNG с гораздо большим выходным диапазоном. Алгоритм Мерсенна Твистера имеет максимальный выход 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;
}
}
}