Случайное число в диапазоне от 0 до n

Question

Учитывая функцию R, которая производит истинные случайные 32-битные числа, мне нужна функция, которая возвращает случайные целые числа в диапазоне от 0 до n, где n произвольно (менее 2^32).

Функция должна производить все значения от 0 до n с равной вероятностью.

Мне нужна функция, выполняемая в постоянное время без инструкций или циклов if, поэтому что-то вроде функции Java Random.nextInt (n) отсутствует.

Я подозреваю, что простой модуль не будет выполнять работу, если n не является силой 2 - я прав?

---

Я принял ответ Джейсона, несмотря на это требует петли неустановленной длительности, так как это, кажется, лучший способ для использования в практике и по существу отвечает на мой вопрос. Однако меня все еще интересуют любые алгоритмы (даже если они менее эффективны), которые будут детерминированными по своему характеру и гарантированно прекратятся, как указал Марк Байерс.

Answer 1

Не отбрасывая некоторые значения из источника, вы не можете этого сделать. Например, набор размеров 2^32 нельзя разбить на три одинаковых размера. Следовательно, это невозможно сделать, не отбрасывая некоторые значения и итерации до тех пор, пока не будет произведено нераспускаемое значение.

Так, просто использовать это (псевдокод):

rng is random number generator produces uniform integers from [0, max) 
compute m = max modulo (n + 1) 
do { 
    draw a random number r from rng 
} while(r >= max - m) 
return r modulo (n + 1) 

Эффективно я выбрасывая верхнюю часть распределения, что вызывает проблемы. Если rng является равномерным на [0, max), то этот алгоритм будет равномерным на [0, n]

Answer 2

То, о чем вы просите, невозможно. Вы не можете разбить 2 ** 32 числа на три набора точно одинакового размера.

Если вы хотите гарантировать абсолютно идеальное равномерное распределение в 0 < = x < n, где n не является степенью 2, тогда вы должны быть готовы вызвать R потенциально бесконечно много раз. На самом деле вам, как правило, требуется только один или два вызова, но теоретически код должен иметь возможность звонить R сколько угодно раз, иначе он не может быть полностью единообразным.

Answer 3

Я не понимаю, почему модуль не будет делать то, что вы хотите? Так как R - это функция, которая производит истинные случайные 32-битные числа, это означает, что каждое число имеет ту же вероятность, что и будет, правильно? Таким образом, если вы используете модуль п:

randomNumber = R() % (n + 1) //EDITED: n+1 to return values from 0-n 

то каждое число от 0 до п имеет одинаковую вероятность!

Answer 4

Вы можете сгенерировать два 32-битных номера и поместить их вместе, чтобы сформировать 64-битное число. В худшем случае сценарий может быть, чем смещен, 0.99999999976716936, если вы не разряжаете номера (если вам нужно число с числом не более 32 бит), что означает, что какое-то число имеет этот коэффициент меньшей вероятности, чем другие.

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

Answer 5

В зависимости от вашей проблемы/использования случайных чисел, возможно, вы можете предварительно распределить свои случайные числа с помощью медленного метода и поместить их в простой массив. Тогда getNextRnd() может просто вернуть следующее в массиве.

Быстрый, фиксированный звонок времени, никаких ветвей, просто теряющая память (что обычно довольно дешево) и время инициализации процесса.