0到n范围内的随机数 [英] Random number in range 0 to n

问题描述

给出一个产生真实的32位随机数的函数R，我想要一个返回0到n范围内的随机整数的函数，其中n是任意的（小于2 ^ 32）。

Given a function R which produces true random 32 bit numbers, I would like a function that returns random integers in the range 0 to n, where n is arbitrary (less than 2^32).

该函数必须以相等的概率产生所有0到n的值。

The function must produce all values 0 to n with equal probability.

我想要一个可以执行的函数在恒定的时间内没有if语句或循环，所以类似Java Random.nextInt（n）函数的东西就消失了。

I would like a function that executes in constant time with no if statements or loops, so something like the Java Random.nextInt(n) function is out.

我怀疑简单的模数不会除非n是2的幂，否则我的工作是正确的吗？

I suspect that a simple modulus will not do the job unless n is a power of 2 -- am I right?

我接受了Jason的答案，尽管它要求持续时间不确定的循环，因为它似乎是在实践中使用的最佳方法，并且基本上回答了我的问题。但是，我仍然对本质上是确定性的并且可以保证终止的任何算法（即使效率较低）仍然感兴趣，例如Mark Byers所指出的。

I have accepted Jason's answer, despite it requiring a loop of undetermined duration, since it appears to be the best method to use in practice and essentially answers my question. However I am still interested in any algorithms (even if less efficient) which would be deterministic in nature and be guaranteed to terminate, such as Mark Byers has pointed to.

推荐答案

如果不从源中丢弃某些值，则无法执行此操作。例如，大小为2 ^ 32的集合不能划分为三个大小相等的集合。因此，如果不丢弃某些值并进行迭代直到生成未丢弃的值，就不可能做到这一点。

Without discarding some of the values from the source, you can not do this. For example, a set of size 2^32 can not be partitioned into three equally sized sets. Therefore, it is impossible to do this without discarding some of the values and iterating until a non-discarded value is produced.

因此，只需使用以下（伪代码）：

So, just use this (pseudocode):

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，最大值）上是统一的，则此算法在上是统一的[0，n]

Effectively I am throwing out the top part of the distribution that causes problems. If rng is uniform on [0, max), then this algorithm will be uniform on [0, n]

这篇关于0到n范围内的随机数的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！