c - 在 C 中生成 INTEGERS 的均匀分布

Question

我编写了一个 C 函数，我认为它从范围为 [rangeLow, rangeHigh]的均匀分布中选择整数，包括在内。这不是家庭作业——我只是在一些嵌入式系统中使用它来做一些有趣的事情。

在我的测试用例中，此代码似乎产生了适当的分布。不过，我并不完全相信实施是正确的。有人可以进行健全性检查并让我知道我是否在这里做错了什么？

//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()

PS我搜索了其他类似的问题。但是，很难过滤掉讨论随机整数而不是随机浮点数的一小部分问题。

score 13 · Accepted Answer

假设 rand() 在 [0..RAND_MAX] 范围内生成一个均匀分布的值 I，而您希望在 [L,H] 范围内生成一个均匀分布的值 O。

假设 I in 的范围是 [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 的可能性是任何其他值的两倍 - 您的方法再次不一致。

生成统一映射的建议方法如下：

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

无符号整数 nRange = (无符号整数)H - (无符号整数)L + 1;
unsigned int nRangeBits= (unsigned int)ceil(log((double(nRange) / log(2.));
生成 nRangeBits 随机位

这可以通过右移 rand() 的结果来轻松实现
确保生成的数字不大于 HL。如果是 - 重复步骤 2。
现在您只需添加 L 即可将生成的数字映射到 O。

score 10 · Accepted Answer

在某些实现中，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;
}

score 3 · Accepted Answer

我认为众所周知 rand() 不是很好。这仅取决于您需要的“随机”数据有多好。

我想你可以写一个测试然后计算卡方值，看看你的统一生成器有多好：

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

根据您的用途（不要将其用于您的在线扑克洗牌器），您可能会考虑使用 LFSR

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

如果您只想要一些伪随机输出，它可能会更快。此外，据说它们可以是统一的，尽管我对数学的研究不足以支持这一说法。

score 1 · Accepted Answer

纠正分布错误的版本（由 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
}

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

range如果它比小得多，这应该可以很好地工作RAND_MAX，否则您将回到问题，即rand()就其低位而言不是一个好的随机数生成器。

c - 在 C 中生成 INTEGERS 的均匀分布

4 回答 4

Related

Reference