什么是一个范围内时，产生无偏随机整数的最优算法？(What is the optimal algor

在这个StackOverflow的问题：

从一系列产生随机整数

接受的答案提出了在给定之间产生的随机整数下述式min和max ，与min和max被包括入范围：

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

但它也表示，

这仍然是对较低的数字略微偏......也有可能使其消除了偏见，以扩展它。

但它并不能解释为什么它朝较低的数字或如何去除偏见偏见。 所以，问题是：这是代内的一个随机整数最优化方法（签字）范围内，而不是依靠任何幻想，只是rand()函数，并在情况下，如果它是最优的，如何去除偏见？

编辑：

我刚刚测试的while通过@Joey建议-loop算法对浮点推断：

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

看到多少均匀“球”被“下落”到和之间的数字“桶”，一个用于测试的浮点外推法和另一个用于正在被分布式while -loop算法。 但结果证明这取决于“球”（和“水桶”）的数量是变化的，所以我不能轻易挑选赢家。 工作代码，可以发现这个Ideone页 。 例如，具有10桶和球100从桶之间的理想的概率的最大偏差小于用于浮点外推法比对while -loop算法（0.04和0.05），但与1000个球，所述的最大偏差while -loop算法较小（0.024和0.011），并与10000个球，浮点外推再次做的更好（0.0034和0.0053），等没有太多的一致性。 那没有的算法始终产生均匀的分布比其它算法更好的可能性的思考，让我对浮点推断瘦，因为它似乎表现得比较快while -loop算法。 因此，它是精细选择浮点算法外推或我testings /结论并不完全正确？

Answer 1:

当从随机数发生器（RAND_MAX + 1）输出的数目是不均匀地在所需的范围（最大值 - 最小值+ 1）整除时出现问题。 由于将有来自随机数一致的映射到输出，某些输出将被映射到多个随机数比其他。 这是不管的映射是怎么做的 - 你可以使用取模，除法，转换成浮点数，无论巫术你可以拿出，基本的问题仍然存在。

问题的幅度非常小，而且要求不高的应用程序通常可以逃脱忽略它。 较小的范围和较大RAND_MAX就是，较不显着的影响就越大。

我把你的示例程序，并调整了它一下。 首先，我创建了一个特殊版本rand ，只有具有0-255的范围，以更好地发挥效果。 我做了一些调整rangeRandomAlg2 。 最后，我改变了“球”的数量1000000改善一致性。 ：你可以在这里看到的结果http://ideone.com/4P4HY

请注意，浮点版本之间产生两个紧紧地组合概率，无论是附近或0.101 0.097，什么都没有。 这是采取行动的偏见。

我想调用这个“Java的算法”是有点误导 - 我敢肯定它比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;
}

Answer 2:

问题是，你正在做一个模操作。 这将是没有问题，如果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更可能的。

解决这个一种选择是拒绝采样：通过禁止数字9和10的上方可以导致生成的分配再次成为均匀的。 最棘手的部分是搞清楚如何使高效地完成。 一个非常好的例子（一说我花了两天的时间理解为什么它的工作原理），可以在Java的发现java.util.Random.nextInt(int)方法。

之所以Java的算法是有点棘手的是，他们避免这样的乘法和除法的检查较慢的操作。 如果你没有太在意你也可以做它用简单的方式：

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;

编辑：修正了栅栏柱错误上面的代码，现在的作品，因为它应该。 我还创建了一个小样本程序（C＃;经由各种方式服用均匀PRNG为数字0和15之间，并构造为PRNG数字0 6之间，并从它）：

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）。 正如你所看到的，浮动的方法是不完美的话，那只是分配偏向号码不同。

Answer 3:

这很容易理解为什么这个算法产生偏差的样本。 假设你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}和再滚动。

Answer 4:

迄今为止最容易的解决方案是std::uniform_int_distribution<int>(min, max) 。

文章来源: What is the optimal algorithm for generating an unbiased random integer within a range?