在C中生成INTEGERS的均匀分布

一尘不染

在C中生成INTEGERS的均匀分布

algorithm

我编写了一个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我搜索了其他类似问题。但是，很难过滤掉讨论随机整数而不是随机浮点数的一小部分问题。

阅读 246

2020-07-28

共1个答案

一尘不染

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

2020-07-28