c++ - 在一个范围内生成无偏随机整数的最佳算法是什么？

Question

在这个 StackOverflow 问题中:

Generating random integer from a range

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

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

但它也这么说

This is still slightly biased towards lower numbers ... It's also possible to extend it so that it removes the bias.

但它没有解释为什么它偏向于较低的数字或如何消除这种偏见。所以，问题是:这是在(有符号)范围内生成随机整数的最佳方法，而不依赖于任何花哨的东西，只是 rand() 函数，如果它是最优，如何消除偏差？

编辑:

我刚刚测试了@Joey 建议的 while-loop 算法对浮点外推:

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

查看有多少“球”均匀地“落入”并分布在多个“桶”中，一个测试用于浮点外推，另一个测试用于 while 循环算法。但是结果会根据“球”(和“桶”)的数量而有所不同，所以我无法轻易选出获胜者。工作代码可以在 this Ideone page 找到.例如，对于 10 个桶和 100 个球，浮点外推法与 while 循环算法(分别为 0.04 和 0.05)相比，在桶之间与理想概率的最大偏差较小，但对于 1000 个球，while-loop 算法的最大偏差更小(0.024 和 0.011)，并且有 10000 个球，浮点外推再次做得更好(0.0034 和 0.0053)，依此类推的一致性。考虑到没有一种算法始终如一地产生比其他算法更好的均匀分布的可能性，这让我倾向于浮点外推，因为它似乎比 while 循环算法执行得更快。那么选择浮点外推算法是否可以，或者我的测试/结论不完全正确？

Answer 1

问题是您正在执行模运算。如果 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#；为 0 到 15 之间的数字采用统一的 PRNG，并通过各种方式从中构造一个用于 0 到 6 之间的数字的 PRNG):

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 方法并不完美，它只是以不同的方式分配有偏的数字。