什么是在一个范围内生成一个无偏随机整数的最佳algorithm？
在这个StackOverflow的问题：
从范围生成随机整数
接受的答案build议在给定的min和max之间生成一个随机整数，其中min和max包含在以下公式中：
output = min + (rand() % (int)(max - min + 1))
但也是这样说的
这仍然略微偏向较低的数字…也可以扩展它，以消除偏见。
但这并不能解释为什么它偏向较低的数字或如何消除偏见。 所以，问题是：这是在一个（有符号）范围内生成一个随机整数的最优方法，而不依赖任何花哨，只是rand()函数，并且如果它是最优的，如何消除偏？
编辑：
我刚刚testing了@Joey针对浮点外推提出的while -loopalgorithm：
static const double s_invRandMax = 1.0/((double)RAND_MAX + 1.0); return min + (int)(((double)(max + 1 - min))*rand()*s_invRandMax);
看看有多less统一的“球”正在“落入”并分布在多个“桶”之中，一个用于浮点外推的testing，另一个用于while loopalgorithm。 但结果却因“球”（和“水桶”）的数量而变化，所以我不能轻易挑选出一个胜利者。 工作代码可以在这个Ideone页面find。 例如，对于10个桶和100个球，对于浮点外推的理想概率的最大偏差对于浮点外推比对于循环的algorithm（分别为0.04和0.05）要小，但对于1000个球，最大偏差-loopalgorithm较小（0.024和0.011），而有10000个球时，浮点外推再次变得更好（0.0034和0.0053）等等，没有太多的一致性。 考虑到没有任何一种algorithm一致地产生均匀分布的可能性比其他algorithm更好，这使得我倾向于浮点外推，因为它似乎比while loopalgorithm执行得更快。 那么select浮点外推algorithm还是不错，或者我的testing/结论不完全正确？
当来自随机数发生器（RAND_MAX + 1）的输出的数量不能被期望的范围（max-min + 1）均匀分割时，就会出现问题。 由于从一个随机数到一个输出会有一个一致的映射，所以有些输出会被映射到比其他随机数更多的随机数。 这是无论如何完成映射 – 你可以使用模，划分，转换为浮点，无论你能想出巫术，基本的问题依然存在。
问题的严重程度非常低，而且要求不高的应用程序通常会忽略它。 范围越小，RAND_MAX越大，效果越不明显。
我把你的示例程序和调整了一下。 首先，我创build了一个只有0-255范围的特殊版本的rand ，以更好地展示效果。 我做了一些调整rangeRandomAlg2 。 最后我把“球”的数量改为1000000，以提高一致性。 你可以在这里看到结果： http : //ideone.com/4P4HY
请注意，浮点版本产生两个紧密分组的概率，接近0.101或0.097，两者之间没有任何内容。 这是行动中的偏见。
我认为调用这个“Java的algorithm”有点误导 – 我相信它比Java更古老。
int rangeRandomAlg2 (int min, int max) { int n = max - min + 1; int remainder = RAND_MAX % n; int x; do { x = rand(); } while (x >= RAND_MAX - remainder); return min + x % n; }
问题是你正在做模操作。 如果RAND_MAX可以被你的模数平分， RAND_MAX这将是没有问题的，但通常情况并非如此。 作为一个非常人为的例子，假设RAND_MAX是11，你的模数是3.你将得到以下可能的随机数和下面的结果余数：
0 1 2 3 4 5 6 7 8 9 10 0 1 2 0 1 2 0 1 2 0 1
正如你所看到的，0和1稍微比2更可能。
解决这个问题的一个select是拒绝抽样：通过不允许上面的数字9和10，可以使得到的分布重新一致。 棘手的部分是搞清楚如何有效地做到这一点。 Java的java.util.Random.nextInt(int)方法中有一个很好的例子（花了我两天的时间来理解它的工作原理）。
Javaalgorithm有点棘手的原因是它避免了像乘法和除法这样的缓慢操作。 如果你不太在乎，你也可以用天真的方式来做：
int n = (int)(max - min + 1); int remainder = RAND_MAX % n; int x, output; do { x = rand(); output = x % n; } while (x >= RAND_MAX - remainder); return min + output;
编辑：在上面的代码更正了fencepost错误，现在它的工作，因为它应该。 我也创build了一个小样本程序（C＃;对0到15之间的数字采用统一的PRNG，并通过各种方式从0到6之间的数字构buildPRNG）：
using System; class Rand { static Random r = new Random(); static int Rand16() { return r.Next(16); } static int Rand7Naive() { return Rand16() % 7; } static int Rand7Float() { return (int)(Rand16() / 16.0 * 7); } // corrected static int Rand7RejectionNaive() { int n = 7, remainder = 16 % n, x, output; do { x = Rand16(); output = x % n; } while (x >= 16 - remainder); return output; } // adapted to fit the constraints of this example static int Rand7RejectionJava() { int n = 7, x, output; do { x = Rand16(); output = x % n; } while (x - output + 6 > 15); return output; } static void Test(Func<int> rand, string name) { var buckets = new int[7]; for (int i = 0; i < 10000000; i++) buckets[rand()]++; Console.WriteLine(name); for (int i = 0; i < 7; i++) Console.WriteLine("{0}\t{1}", i, buckets[i]); } static void Main() { Test(Rand7Naive, "Rand7Naive"); Test(Rand7Float, "Rand7Float"); Test(Rand7RejectionNaive, "Rand7RejectionNaive"); } }
结果如下（粘贴到Excel中，并添加了单元格的条件着色，使差异更加明显）：
现在我在上面的拒绝采样中修正了我的错误，它应该（在它偏向0之前）工作。 正如你所看到的，float方法并不完美，它只是以不同的方式分配偏倚的数字。
很容易看出为什么这个algorithm产生了一个有偏差的样本。 假设你的rand()函数从集合{0, 1, 2, 3, 4}返回一致的整数。 如果我想用这个来产生一个随机位0或1 ，我会说rand() % 2 。 集合{0, 2, 4}给我0 ，集合{1, 3}给我1 – 很明显我抽样0有60％和1有40％的可能性，根本不统一！
为了解决这个问题，你必须确保你所希望的范围除了随机数发生器的范围，否则，只要随机数发生器返回一个大于目标范围的最大可能倍数的数字就舍弃结果。
在上例中，目标范围是2，适合随机生成范围的最大倍数是4，因此我们丢弃任何不在集合{0, 1, 2, 3}中的样本并再次滚动。
到目前为止，最简单的解决scheme是std::uniform_int_distribution<int>(min, max) 。
