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

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

Мне нужно сгенерировать случайное число от 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?
4 3
language-agnostic random discrete-mathematics

4 ответа:

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

3

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

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

2

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

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

1

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

Мое эмпирическое правило состоит в том, чтобы генерировать значения с плавающей запятой, x, 0.0 x

0