在C语言中生成一个整数的均匀分布

Question

我编写了一个C函数，它可以从范围为[rangeLow, rangeHigh]（包括边界）的均匀分布中选择整数。这不是作业 - 我只是在进行一些嵌入式系统 tinkering 的时候使用它来玩乐。

在我的测试案例中，此代码似乎产生了适当的分布。然而，我并不完全自信这个实现是正确的。能否有人对其进行审核，并让我知道是否有任何错误？

//uniform_distribution returns an INTEGER in [rangeLow, rangeHigh], inclusive.
int uniform_distribution(int rangeLow, int rangeHigh)
{
    int myRand = (int)rand(); 
    int range = rangeHigh - rangeLow + 1; //+1 makes it [rangeLow, rangeHigh], inclusive.
    int myRand_scaled = (myRand % range) + rangeLow;
    return myRand_scaled;
}
//note: make sure rand() was already initialized using srand()

附言：我搜索了其他类似的问题，但是很难过滤掉讨论随机整数而不是随机浮点数的小子集的问题。

- solvingPuzzles

---

为了获得良好的随机性，您可能需要选择一些特定于平台的东西，或者至少使用标准C之外的东西，例如POSIX或BSD规范函数。 - dreamlax

Answer 1

假设rand()生成在范围[0..RAND_MAX]内均匀分布的值I，且您想要生成在范围[L,H]内均匀分布的值O。

假设I在范围[0..32767]内，O在范围[0..2]内。

根据您提出的方法，O=I%3。请注意，给定范围内，有10923个数字使得I%3=0，有10923个数字使得I%3=1，但只有10922个数字使得I%3=2。因此，您的方法将无法将一个值从I映射到O上。

再举一个例子，假设O在范围[0..32766]内。

根据您提出的方法，O=I%32767。现在，对于I=0和I=32767，您将得到O=0。因此，0的概率是其他任何值的两倍- 您的方法再次是不均匀的。

建议生成均匀映射的方法如下：

1. 计算存储在范围[L,H]内的随机值所需的位数：

unsigned int nRange = (unsigned int)H - (unsigned int)L + 1; unsigned int nRangeBits= (unsigned int)ceil(log((double)nRange) / log(2.));

2. 生成nRangeBits个随机位

这可以通过右移rand()的结果来轻松实现

3. 确保生成的数字不大于H - L。如果是- 请重复步骤2。

4. 现在，您可以通过添加L来将生成的数字映射到O上。

- Lior Kogan

---

我已经在这里引用了这个好答案（https://codereview.stackexchange.com/a/184447/29485）。小的候选改进是 ceil(log((double(nRange) / log(2.)) --> ceil(log2((double)nRange)) 或者其他整数计算。 - chux - Reinstate Monica

Answer 2

在一些实现中，rand()函数的低位不够随机, 因此取模运算符可能不会提供很随机的结果。如果你发现这是个问题，你可以尝试使用以下方法代替：

int uniform_distribution(int rangeLow, int rangeHigh) {
    double myRand = rand()/(1.0 + RAND_MAX); 
    int range = rangeHigh - rangeLow + 1;
    int myRand_scaled = (myRand * range) + rangeLow;
    return myRand_scaled;
}

使用rand()这种方式会产生偏差，正如Lior所指出的那样。但是，如果您可以找到一个均匀的数字生成器来计算myRand，那么该技术是可以使用的。一个可能的候选者是drand48()。这将大大减少偏差量，使其变得非常难以检测。

然而，如果您需要安全加密的东西，则应该使用Lior回答中概述的算法，假设您的rand()本身是加密安全的（默认值可能不是，因此您需要找到一个）。下面是Lior所描述的简化实现。我们假设范围在RAND_MAX内，并计算适当的倍数。最坏情况下，算法每个请求的数字平均会调用两次随机数生成器。

int uniform_distribution_secure(int rangeLow, int rangeHigh) {
    int range = rangeHigh - rangeLow + 1;
    int secureMax = RAND_MAX - RAND_MAX % range;
    int x;
    do x = secure_rand(); while (x >= secureMax);
    return rangeLow + x % range;
}

- jxh

---

应该是 "return rangeLow + x % range;"。 - Marc

Answer 3

我认为大家都知道rand()函数并不是很好。它只取决于你需要多好的“随机”数据。

• http://www.azillionmonkeys.com/qed/random.html
• http://www.linuxquestions.org/questions/programming-9/generating-random-numbers-in-c-378358/
• http://forums.indiegamer.com/showthread.php?9460-Using-C-rand%28%29-isn-t-as-bad-as-previously-thought

我想你可以编写一个测试，然后计算卡方值来判断你的均匀生成器的好坏：

http://en.wikipedia.org/wiki/Pearson%27s_chi-squared_test

根据您的用途（不要在您的在线扑克洗牌器中使用此方法），您可以考虑使用LFSR。

http://en.wikipedia.org/wiki/Linear_feedback_shift_register

如果你只需要一些伪随机输出，使用它可能会更快。此外，据说它们可以是均匀的，尽管我还没有研究足够的数学知识来支持这种说法。

- Josh Petitt

Answer 4

一种修正分布错误（由Lior指出）的版本，涉及rand()返回的高位，并且仅使用整数运算（如果需要的话）：

int uniform_distribution(int rangeLow, int rangeHigh)
{
    int range = rangeHigh - rangeLow + 1; //+1 makes it [rangeLow, rangeHigh], inclusive.
    int copies=RAND_MAX/range; // we can fit n-copies of [0...range-1] into RAND_MAX
    // Use rejection sampling to avoid distribution errors
    int limit=range*copies;    
    int myRand=-1;
    while( myRand<0 || myRand>=limit){
        myRand=rand();   
    }
    return myRand/copies+rangeLow;    // note that this involves the high-bits
}

//注意：确保已使用srand()初始化了rand()

只要range比RAND_MAX小得多，这应该能很好地工作，否则你将会回到rand()在其低位方面不是一个好的随机数生成器的问题。

- Dave

---

你的意思是 myRand < 0 || myRand >= limit，对吧？为什么不使用 do while 呢？ - Marc

@Marc 我系统地使用半开区间来处理这种东西；请参阅https://www.cs.utexas.edu/users/EWD/transcriptions/EWD08xx/EWD831.html，并避免将do-while作为我的“风格”的一部分。 - Dave

好的 Dave，但是我的 myRand 永远不会同时小于 0 和大于等于限制。 - Marc