Равномерно распределенные случайные числа относительно простых 2

Question

Конкретный пример

Мне нужно сгенерировать случайное число от 0 до 2 включительно. (или выберите случайным образом между -1, 0 и 1).

Наивным подходом было бы сделать что-то вроде rand() mod 3, где rand() возвращает целое число. Этот подход не будет генерировать статистически случайные числа, если верхняя граница rand() не является относительно простой (а нижняя граница равна 0).

Например, предполагая, что rand () вернул 2 бита (от 0 до 3 включительно), модуль будет отображаться:

0 -> 0
1 -> 1
2 -> 2
3 -> 0

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

Общий вопрос

Есть ли способ генерирования равномерно распределенного случайного числа между 0 и n-1 включительно, где n относительно простого числа 2?

Answer 1

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

Answer 2

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

Если невозможно уменьшить верхнюю границу, вы можете выбрать k так, чтобы k * n был как можно ближе к верхней границе rand (), и отбросить результаты выше этого числа, повторив попытку.

Answer 3

См. мой ответ на аналогичный вопрос.

В основном, используйте свой ГСЧ, откажитесь от всего, что выше N, и попробуйте снова. Для оптимизации вы можете использовать мод и отбросить все, что выше n * floor (MAX / n)

Answer 4

Общий ответ: вам нужно использовать больше, чем просто 2 бита числа.

Мое эмпирическое правило - генерировать значения с плавающей запятой, x , 0,0 <= <em>x <1,0, умножить на 3 и усечь. Это должно получить значения в диапазоне 0, 1 и 2, которые зависят от большего числа битов. </p>