如何从一个范围内生成一个随机数

这是以前发布的问题的后续内容:

如何在C中生成一个随机数?

我希望能够在一个特定的范围内产生一个随机数,例如1到6来模仿一个骰子的边。

我怎么去做这个?

到目前为止所有的答案在math上是错误的。 如果N除以rand()返回的区间的长度(即2的幂),则返回rand() % N不会统一给出范围[0, N)内的数字。 此外,人们不知道rand()的模是否是独立的:它们有可能是0, 1, 2, ... ,这是均匀的,但不是很随机的。 似乎合理的唯一假设是rand()了一个泊松分布:相同大小的任何两个不重叠的子区间是等可能和独立的。 对于一组有限的值,这意味着均匀分布,并且还确保rand()的值很好地分散。

这意味着改变rand()的范围的唯一正确的方法是将其分成多个盒子; 例如,如果RAND_MAX == 11并且您希望范围为1..6 ,则应该将{0,1}分配给1,将{2,3}分配给2,依此类推。 这些是不相交的,大小相同的区间,因此是均匀和独立分布的。

使用浮点除法的build议在math上似乎是合理的,但原则上受到舍入问题的困扰。 也许double是足够高的精度,使其工作; 也许不是。 我不知道,也不想弄清楚。 在任何情况下,答案都是系统相关的。

正确的方法是使用整数算术。 就是说,你需要像下面这样的东西:

 #include <stdlib.h> // For random(), RAND_MAX // Assumes 0 <= max <= RAND_MAX // Returns in the closed interval [0, max] long random_at_most(long max) { unsigned long // max <= RAND_MAX < ULONG_MAX, so this is okay. num_bins = (unsigned long) max + 1, num_rand = (unsigned long) RAND_MAX + 1, bin_size = num_rand / num_bins, defect = num_rand % num_bins; long x; do { x = random(); } // This is carefully written not to overflow while (num_rand - defect <= (unsigned long)x); // Truncated division is intentional return x/bin_size; } 

循环是获得完全一致的分布所必需的。 例如,如果您给予从0到2的随机数,而您只需要从0到1的数,那么您只需一直拉,直到您没有得到2; 不难看出这给出0或1的概率相等。 这个方法也被描述在nos给出的答案中,尽pipe编码方式不同。 我使用random()而不是rand()因为它具有更好的分布(如rand()手册页所述)。

如果你想获得超出默认范围[0, RAND_MAX]随机值,那么你必须做一些棘手的事情。 也许最方便的是定义一个函数random_extended() ,它将n位(使用random_at_most() )并返回[0, 2**n) ,然后用random_at_most()random_extended() random() (和2**n - 1代替RAND_MAX )来拉一个小于2**n的随机值,假设你有一个可以保存这个值的数字types。 最后,当然,您可以使用min + random_at_most(max - min)获取[min, max]值,包括负值。

继@Ryan Reich的回答之后,我想我会提供我的清理版本。 第一次边界检查是不需要的第二次边界检查,我已经做了迭代,而不是recursion。 它返回范围[min,max]中的值,其中max >= min1+max-min < RAND_MAX

 unsigned int rand_interval(unsigned int min, unsigned int max) { int r; const unsigned int range = 1 + max - min; const unsigned int buckets = RAND_MAX / range; const unsigned int limit = buckets * range; /* Create equal size buckets all in a row, then fire randomly towards * the buckets until you land in one of them. All buckets are equally * likely. If you land off the end of the line of buckets, try again. */ do { r = rand(); } while (r >= limit); return min + (r / buckets); } 
 unsigned int randr(unsigned int min, unsigned int max) { double scaled = (double)rand()/RAND_MAX; return (max - min +1)*scaled + min; } 

在这里查看其他选项。

如果您知道范围的最大值和最小值,并且您希望在范围之间生成包含的数字,则这是一个公式:

 r = (rand() % (max + 1 - min)) + min 

你不会这么做吗:

 srand(time(NULL)); int r = ( rand() % 6 ) + 1; 

%是模数运算符。 从本质上讲,它只会被分成6份,然后从0 – 5中归还剩下的部分

对于那些理解偏差问题但不能忍受基于拒绝方法的不可预测的运行时间的人来说,这个序列在[0, n-1]区间内产生一个逐渐减less的随机整数:

 r = n / 2; r = (rand() * n + r) / (RAND_MAX + 1); r = (rand() * n + r) / (RAND_MAX + 1); r = (rand() * n + r) / (RAND_MAX + 1); ... 

它通过合成i * log_2(RAND_MAX + 1)位(其中i是迭代次数)的高精度定点随机数并执行长乘n

当比特数与n相比足够大时,偏差变得不可观测地小。

如果RAND_MAX + 1小于n (如在这个问题中 ),或者它不是2的幂次,那么无关紧要,但是如果RAND_MAX * n很大,必须注意避免整数溢出。

为了避免模偏差(在其他答案中build议),您可以始终使用:

 arc4random_uniform(MAX-MIN)+MIN 

其中“MAX”是上限,“MIN”是下限。 例如,对于10到20之间的数字:

 arc4random_uniform(20-10)+10 arc4random_uniform(10)+10 

简单的解决scheme,比使用“rand()%N”更好。

这里比Ryan Reich的解决scheme稍微简单一些:

 /// Begin and end are *inclusive*; => [begin, end] uint32_t getRandInterval(uint32_t begin, uint32_t end) { uint32_t range = (end - begin) + 1; uint32_t limit = (RAND_MAX + 1) - ((RAND_MAX + 1) % range); /* Imagine range-sized buckets all in a row, then fire randomly towards * the buckets until you land in one of them. All buckets are equally * likely. If you land off the end of the line of buckets, try again. */ uint32_t randVal = rand(); while (randVal >= limit) randVal = rand(); /// Return the position you hit in the bucket + begin as random number return (randVal % range) + begin; } 

 Example (RAND_MAX := 16, begin := 2, end := 7) => range := 6 (1 + end - begin) => limit := 12 (RAND_MAX + 1) - ((RAND_MAX + 1) % range) The limit is always a multiple of the range, so we can split it into range-sized buckets: Possible-rand-output: 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 Buckets: [0, 1, 2, 3, 4, 5][0, 1, 2, 3, 4, 5][X, X, X, X, X] Buckets + begin: [2, 3, 4, 5, 6, 7][2, 3, 4, 5, 6, 7][X, X, X, X, X] 1st call to rand() => 13 → 13 is not in the bucket-range anymore (>= limit), while-condition is true → retry... 2nd call to rand() => 7 → 7 is in the bucket-range (< limit), while-condition is false → Get the corresponding bucket-value 1 (randVal % range) and add begin => 3 

虽然Ryan是正确的,但是基于对随机性来源的了解,解决scheme可以简单得多。 重新说明问题:

  • 有一个随机性来源,输出范围[0, MAX)
  • 目标是在范围[rmin, rmax]中产生均匀分布的随机数,其中0 <= rmin < rmax < MAX

根据我的经验,如果箱子(或“箱子”)的数量明显小于原始数量的范围,而且原始数据源的密码强度更大,那么就不需要经过所有这些巨大的数量,而简单的模块划分足够的(如output = rnd.next() % (rmax+1) ,如果rmin == 0 ),并产生均匀分布的“足够”的随机数,没有任何速度的损失。 关键因素是随机性来源(即孩子们,不要在家里用rand()试试这个)。

这是一个在实践中如何工作的例子/certificate。 我想生成从1到22的随机数,有一个密码强的源产生随机字节(基于英特尔RDRAND)。 结果是:

 Rnd distribution test (22 boxes, numbers of entries in each box): 1: 409443 4.55% 2: 408736 4.54% 3: 408557 4.54% 4: 409125 4.55% 5: 408812 4.54% 6: 409418 4.55% 7: 408365 4.54% 8: 407992 4.53% 9: 409262 4.55% 10: 408112 4.53% 11: 409995 4.56% 12: 409810 4.55% 13: 409638 4.55% 14: 408905 4.54% 15: 408484 4.54% 16: 408211 4.54% 17: 409773 4.55% 18: 409597 4.55% 19: 409727 4.55% 20: 409062 4.55% 21: 409634 4.55% 22: 409342 4.55% total: 100.00% 

这是为了我的目的(公平的投掷骰子,为第二次世界大战密码机制造密码强的密码本,如http://users.telenet.be/d.rijmenants/en/kl-7sim.htm等)。; 输出不显示任何可观的偏见。

下面是密码强(真)随机数发生器的来源: 英特尔数字随机数发生器和一个产生64位(无符号)随机数的示例代码。

 int rdrand64_step(unsigned long long int *therand) { unsigned long long int foo; int cf_error_status; asm("rdrand %%rax; \ mov $1,%%edx; \ cmovae %%rax,%%rdx; \ mov %%edx,%1; \ mov %%rax, %0;":"=r"(foo),"=r"(cf_error_status)::"%rax","%rdx"); *therand = foo; return cf_error_status; } 

我在Mac OS X上用clang-6.0.1(直线)编译,用gcc-4.8.3用“-Wa,q”标记(因为GAS不支持这些新的指令)。

如前所述,模数是不够的,因为它扭曲了分布。 inheritance人我的代码掩盖了一些位,并使用它们来确保分配不倾斜。

 static uint32_t randomInRange(uint32_t a,uint32_t b) { uint32_t v; uint32_t range; uint32_t upper; uint32_t lower; uint32_t mask; if(a == b) { return a; } if(a > b) { upper = a; lower = b; } else { upper = b; lower = a; } range = upper - lower; mask = 0; //XXX calculate range with log and mask? nah, too lazy :). while(1) { if(mask >= range) { break; } mask = (mask << 1) | 1; } while(1) { v = rand() & mask; if(v <= range) { return lower + v; } } } 

下面的简单代码可以让你看看分布:

 int main() { unsigned long long int i; unsigned int n = 10; unsigned int numbers[n]; for (i = 0; i < n; i++) { numbers[i] = 0; } for (i = 0 ; i < 10000000 ; i++){ uint32_t rand = random_in_range(0,n - 1); if(rand >= n){ printf("bug: rand out of range %u\n",(unsigned int)rand); return 1; } numbers[rand] += 1; } for(i = 0; i < n; i++) { printf("%u: %u\n",i,numbers[i]); } }