在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我搜索了这样的其他问题.但是,很难过滤掉讨论随机整数而不是随机浮点数的小问题子集.

Answer 1

假设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是任何其他值的两倍 - 您的方法再次不均匀.

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

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. 确保生成的数字不大于HL.如果是 - 重复步骤2.

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

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().这将极大地减少对非常难以检测的东西的偏见量.

但是,如果你需要的东西加密的安全,你应该使用在利奥尔的回答概括的算法,假设你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;
}