快速安全地确定范围内的随机数

Question

我将如何快速和安全*确定范围内的随机数0(含)至r(独家)？

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

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

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

    return(ret);
}

*安全地,我的意思是统一分布.

Answer 1

如果要在结果上进行均匀分布,则拒绝抽样是可行的方法.众所周知,做任何更聪明的事情是很困难的.例如,使用模运算符会导致任何不是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 ³¹不能被n整除).值被拒绝的概率取决于n.最坏的情况是n = 2 ³⁰ +1,其中拒绝的概率是1/2,并且循环终止之前的预期迭代次数是2.