在 C 中生成 INTEGERS 的均匀分布 [英] Generating a uniform distribution of INTEGERS in C

问题描述

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

I've written a C function that I think selects integers from a uniform distribution with range [rangeLow, rangeHigh], inclusive. This isn't homework--I'm just using this in some embedded systems tinkering that I'm doing for fun.

在我的测试用例中，此代码似乎产生了适当的分布.不过，我并不完全相信实施是正确的.如果我在这里做错了什么，有人可以进行完整性检查并告诉我吗?

In my test cases, this code appears to produce an appropriate distribution. I'm not feeling fully confident that the implementation is correct, though. Could someone do a sanity check and let me know if I've done anything wrong here?

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

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

P.S. I searched for other questions like this. However, it was hard to filter out the small subset of questions that discuss random integers instead of random floating-point numbers.

推荐答案

在某些实现中，rand() 没有在其低位提供良好的随机性，因此模运算符不会提供非常随机结果.如果你发现是这种情况，你可以试试这个:

On some implementations, rand() did not provide good randomness on its lower order bits, so the modulus operator would not provide very random results. If you find that to be the case, you could try this instead:

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() 是一种可能的候选者.这将大大减少对难以检测的事物的偏差量.

Using rand() this way will produce a bias as noted by Lior. But, the technique is fine if you can find a uniform number generator to calculate myRand. One possible candidate would be drand48(). This will greatly reduce the amount of bias to something that would be very difficult to detect.

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

However, if you need something cryptographically secure, you should use an algorithm outlined in Lior's answer, assuming your rand() is itself cryptographically secure (the default one is probably not, so you would need to find one). Below is a simplified implementation of what Lior described. Instead of counting bits, we assume the range falls within RAND_MAX, and compute a suitable multiple. Worst case, the algorithm ends up calling the random number generator twice on average per request for a number in the range.

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;
}

这篇关于在 C 中生成 INTEGERS 的均匀分布的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！