2

我如何快速安全地*确定0(包括)到(不包括)范围内的随机数r

换句话说,拒绝抽样的优化版本:

u32 myrand(u32 x)
{
    u32 ret = rand();

    while(ret >= x)
        ret = rand();

    return(ret);
}

*安全,我的意思是均匀分布。

4

2 回答 2

6

如果您想对结果进行均匀分布,则拒绝抽样是一种方法。众所周知,做任何更聪明的事情都是困难的。例如,使用模运算符会导致任何不是 2 的幂的数字的结果值分布不均匀。

但是,您发布的算法可以通过丢弃不必要的最高有效位来改进。(见下文。)

这就是标准 Java API 的实现方式Random.nextInt(int n)

public int nextInt(int n) {

    [...]

    if ((n & -n) == n)  // i.e., n is a power of 2
        return (int)((n * (long)next(31)) >> 31);

    int bits, val;
    do {
        bits = next(31);
        val = bits % n;
    } while (bits - val + (n-1) < 0);

    return val;
}

在评论中您可以阅读:

该算法有点棘手。它拒绝会导致分布不均匀的值(因为 2 31不能被n整除)。一个值被拒绝的概率取决于 n。最坏的情况是n =2 30 +1,拒绝的概率是 1/2,循环终止前的预期迭代次数是 2。

于 2011-06-17T05:47:53.017 回答
-1
u32 myrand(u32 x)
{
    return rand() % (x+1);
}

由于问题已更改为包括均匀分布,因此需要更多类似的内容:

u32 myrand(u32 x)
{
   assert(x <= RAND_MAX && x > 0);
   int numOfRanges = (RAND_MAX % x);
   int maxAcceptedRand = numOfRanges * x;
   int randNumber;
   do
   {
      randNumber = rand();
   }
   while(randNumber <= maxAcceptedRand);
   return number / numOfRanges;
}
于 2011-06-17T05:46:01.227 回答