在一个范围内产生一个无偏随机整数的最优算法是什么？

Question

接受的答案建议使用以下公式，用于在给定的min和max之间生成一个随机整数，其中min和max包括在范围内：

output = min + (rand() % (int)(max - min + 1))

但它也说

这仍然是稍微偏向较低的数字...也可以扩展它，这样它就可以消除这种偏向。

static const double s_invRandMax = 1.0/((double)RAND_MAX + 1.0);
return min + (int)(((double)(max + 1 - min))*rand()*s_invRandMax);

Answer 1

当随机数发生器的输出数(RAND_MAX+1)不能被所需范围(max-min+1)均匀整除时，就会出现问题。由于将存在从随机数到输出的一致映射，因此某些输出将映射到比其他输出更多的随机数。不管映射是如何完成的--你可以使用模，除法，到浮点的转换，无论你能想出什么巫毒，基本问题仍然存在。

这个问题的规模很小，要求不高的应用程序通常可以忽略它。范围越小且RAND_MAX越大，则效果越不明显。

我以您的示例程序为例，对其进行了一些调整。首先，我创建了rand的特殊版本，它的范围仅为0-255，以更好地演示效果。我对rangerandomalg2做了一些调整。最后我将“球”的数量改为1000000以提高一致性。您可以在这里看到结果:http://ideone.com/4p4hy

int rangeRandomAlg2 (int min, int max)
{
    int n = max - min + 1;
    int remainder = RAND_MAX % n;
    int x;
    do
    {
        x = rand();
    } html" target="_blank">while (x >= RAND_MAX - remainder);
    return min + x % n;
}