生成整数的C语言的均匀分布 [英] Generating a uniform distribution of INTEGERS in C

问题描述

我已经写了一个C函数，我认为选择从均匀分布与范围[rangeLow，rangeHigh]整数，包容性。这不是功课 - I'm只是用这种方式是嵌入式系统修修补补，我做的乐趣

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.

在我的测试情况下，code能够产生相应的分配。我感觉不完全相信，实施是正确的，但。 可能有人做了仔细的检查，让我知道，如果我做错了什么吗？

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

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.

推荐答案

在一些实现，兰特（）并没有提供良好的随机性其低阶位，因此，模运营商不会提供非常随机的结果。如果发现是这种情况，你可以试试这个：

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

使用兰特（）这种方式会产生偏差所指出的利奥尔。但是，该技术是好的，如果你能找到一个统一数生成器来计算 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.

不过，如果你需要的东西加密的安全，你应该使用利奥尔的回答中概述的算法，假设你的兰特（）本身是加密安全（默认的可能没有，所以你需要找到一个）。下面是一个什么利奥尔描述的简化实施。相反计数位，我们假定范围落在 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 = 1 + (RAND_MAX - RAND_MAX % range);
    int x;
    do x = secure_rand(); while (x > secureMax);
    return rangeLow + x / range;
}

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