Как правильно ограничить псевдослучайное число меньшим диапазоном?

Question

Как лучше всего ограничить значения PRNG меньшим диапазоном? Если вы используете модуль, а старое максимальное число не делится поровну на новое максимальное число, которое вы смещаете в сторону от 0 до (old_max - new_max - 1). Я предполагаю, что лучшим способом было бы что-то вроде этого (это с плавающей точкой, а не целочисленная математика)

random_num = PRNG() / max_orginal_range * max_smaller_range

но что-то в моей голове заставляет меня задаться вопросом об этом методе (может быть, реализация с плавающей запятой и различия в представлении?).

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

Я был прав, когда усомнился в псевдокоде выше (но не по тем причинам, о которых я думал). ответ MichaelGG заставил меня задуматься о проблеме по-другому. Я могу смоделировать это, используя меньшие числа и проверить каждый результат. Итак, давайте предположим, что у нас есть PRNG, который генерирует случайное число от 0 до 31, и вы хотите, чтобы меньший диапазон был от 0 до 9. Если вы используете модуль, вы смещаете в сторону 0, 1, 2 и 3. Если вы используете псевдокод выше вас смещение в сторону 0, 2, 5 и 7. Я не думаю, что может быть хороший способ отобразить один набор в другой. Лучшее, что я придумала до сих пор, - это регенерирование случайных чисел, которые больше old_max/new_max, но у них также есть серьезные проблемы (сокращение периода, времени для генерации новых чисел, пока один не окажется в нужном диапазоне, и т. Д.). .).

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

Answer 1

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

Если сомневаетесь, попробуйте сами.

EDIT

Следует отметить, что многие языки (например, C #) имеют встроенные ограничения в своих функциях

int maximumvalue = 20;
Random rand = new Random();

rand.Next(maximumvalue);

И всякий раз, когда это возможно, вы должны использовать их, а не любой код, который вы написали бы сами. Не изобретай колесо.

Answer 2

Генераторы случайных чисел Псуэдо по сути производят случайные серии из 1 и 0, которые при добавлении друг к другу представляют собой бесконечно большое число в базе два. каждый раз, когда вы немного потребляете, вы делите это число на два и сохраняете модуль. Вы можете делать это вечно, не теряя ни единого бита.

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

Answer 3

Вот как работает класс Random CLR, когда он ограничен (согласно отражателю):

long num = maxValue - minValue;
if (num <= 0x7fffffffL) {
    return (((int) (this.Sample() * num)) + minValue);
}
return (((int) ((long) (this.GetSampleForLargeRange() * num))) + minValue);

Даже если вам дали положительное значение int, нетрудно довести его до двойного. Просто умножьте случайное int на (1 / maxint). Переход от 32-разрядного типа int к двойному должен обеспечить адекватную точность. (Я на самом деле не тестировал такой PRNG, так что я мог бы что-то упустить с плавающей точкой.)

Answer 4

Если у вас есть доступ к функции PRNG (скажем, random ()), которая генерирует числа в диапазоне 0 <= x <1, вы не можете просто сделать: </p>

 random_num = (int) (random() * max_range);

чтобы дать вам числа в диапазоне от 0 до max_range?

Answer 5

Если PRNG () генерирует равномерно распределенные случайные числа, то вышеприведенное выглядит хорошо. На самом деле (если вы хотите масштабировать среднее значение и т. Д.) Вышеприведенное должно подойти для всех целей. Я полагаю, вам нужно спросить, в чем заключается ошибка, связанная с исходным PRNG (), и существенно ли к этому прибавятся дальнейшие манипуляции.

Если вы сомневаетесь, сгенерируйте выборочный набор подходящего размера и посмотрите на результаты в Excel или аналогичном (чтобы проверить, что вы ожидаете), 1003 *