Как смещение проявляется при генерации ограниченного случайного числа

Question

Я пытаюсь переварить следующий пост https://www.pcg-random.org/posts/bounded-rands.html о беспристрастном, эффективном генерировании случайных чисел.

Вот выдержка, описывающая классический подход по модулю.

uint32_t bounded_rand(rng_t& rng, uint32_t range) {
    return rng() % range;
}

Но помимо того, что он медленный, он также смещен. Чтобы понять, почему rand ()% 52 производит смещенные числа, если предположить, что rand () производит числа в диапазоне [0..2 ^ 32), заметим, что 52 не делит идеально 2 ^ 32, а делит его на 82 595 524 раза остаток 48. Это означает, что если мы используем rand ()% 52, будет 82 595 525 способов выбора первых 48 карт из нашей колоды из 52 карт и только 82 595 524 способа выбора последних четырех карт. Другими словами, есть смещение 0,00000121% по отношению к этим последним четырем картам ...

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

static uint32_t bounded_rand(rng_t& rng, uint32_t range) {
    double zeroone = 0x1.0p-32 * rng();
    return range * zeroone;
}

Этот подход столь же смещен, как и классический c по модулю, но смещение проявляется по-разному. Например, если бы мы выбирали числа в диапазоне [0..52), числа 0, 13, 26 и 39 появлялись бы один раз реже, чем другие.

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

Answer 1

Давайте начнем с малого. Скажем, у нас есть метод rng(), который генерирует любое случайное целое число в [0, 128). Если мы отобразим все его 128 результатов следующим образом (где X - один из этих результатов):

 floor((X / 128.0) * 52)

Тогда мы получим следующую таблицу:

 0, 0, 0, 1, 1, 2, 2, 2, 3, 3, 4, 4, 4, 5, 5, 6, 6, 6, 7, 7, 8, 8, 8, 9, 9, 10, 10, 10, 11, 11, 12, 12, 13, 13, 13, 14, 14, 15, 15, 15, 16, 16, 17, 17, 17, 18, 18, 19, 19, 19, 20, 20, 21, 21, 21, 22, 22, 23, 23, 23, 24, 24, 25, 25, 26, 26, 26, 27, 27, 28, 28, 28, 29, 29, 30, 30, 30, 31, 31, 32, 32, 32, 33, 33, 34, 34, 34, 35, 35, 36, 36, 36, 37, 37, 38, 38, 39, 39, 39, 40, 40, 41, 41, 41, 42, 42, 43, 43, 43, 44, 44, 45, 45, 45, 46, 46, 47, 47, 47, 48, 48, 49, 49, 49, 50, 50, 51, 51

Обратите внимание, что встречаются некоторые числа дважды в этой таблице, остальные три раза. Это потому, что мы отображаем большой диапазон на маленький, а 128 не делится на 52, а также из-за ошибки округления. В этом примере 52, деленное на 128, составляет примерно 0,4, поэтому следующая запись в таблице - это предыдущая запись плюс примерно 0,4, затем все записи в таблице округляются в меньшую сторону, создавая некоторые числа, которые встречаются чаще, чем другие. С другой стороны, если бы мы использовали 64 вместо 52, то все 64 записи в таблице из 128 элементов появятся ровно в два раза.

См. Также " Быстрая альтернатива уменьшению по модулю Даниэль Лемир.

---

Вот как детально была сформирована таблица выше. Если вместо этого мы отобразили эти результаты следующим образом:

X / 128.0

Тогда начало таблицы будет выглядеть следующим образом:

0.000, 0.008, 0.016, 0.023, 0.031, 0.039, 0.047, 0.055, 0.062, 0.070, 0.078, 0.086, 0.094, 0.102, 0.109, 0.117, 0.125, 0.133, ...

Если мы умножим эту таблицу на 52, теперь она будет выглядеть следующим образом :

0.000, 0.406, 0.812, 1.219, 1.625, 2.031, 2.438, 2.844, 3.250, 3.656, 4.062, 4.469, 4.875, 5.281, 5.688, 6.094, 6.500, 6.906, 7.312, ...

И, наконец, мы округлим вниз, чтобы получить:

0, 0, 0, 1, 1, 2, 2, 2, 3, 3, 4, 4, 4, 5, 5, 6, 6, 6, 7, ...