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

这是之前发布的一个问题的后续内容:

如何在 C 语言中生成一个随机数？

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

How would I go about doing this?

346195 次浏览
小开

你就不能:

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

%是模运算符。本质上它只需要除以6，然后返回0-5的余数

小开 
unsigned int
randr(unsigned int min, unsigned int max)
{
double scaled = (double)rand()/RAND_MAX;


return (max - min +1)*scaled + min;
}

有关其他选项，请参见 here。

小开

下面是一个公式，如果你知道一个范围的最大值和最小值，并且你想生成包含在这个范围之间的数字:

r = (rand() % (max + 1 - min)) + min
小开
最佳答案

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

这意味着改变 rand()范围的唯一正确方法是将它划分为几个框; 例如，如果 RAND_MAX == 11和您想要 1..6范围，您应该将 {0,1}分配给1，{2,3}分配给2，以此类推。这些是不相交的，大小相等的区间，因此是均匀和独立分布的。

使用浮点除法的建议在数学上是合理的，但在原则上存在舍入问题。也许 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的1，你只需要一直拉，直到你得不到一个2; 不难检查这个给出的0或1的概率是否相等。这个方法也在 nos 给出的答案中的链接中描述，尽管编码不同。我使用的是 random()而不是 rand()，因为它有更好的发行版(正如 rand()的手册页所指出的那样)。

If you want to get random values outside the default range [0, RAND_MAX], then you have to do something tricky. Perhaps the most expedient is to define a function random_extended() that pulls n bits (using random_at_most()) and returns in [0, 2**n), and then apply random_at_most() with random_extended() in place of random() (and 2**n - 1 in place of RAND_MAX) to pull a random value less than random_extended()0, assuming you have a numerical type that can hold such a value. Finally, of course, you can get values in random_extended()1 using random_extended()2, including negative values.

小开

接着@Ryan Reich 的回答，我想我应该提供一个清理过的版本。给定第二个边界检查，第一个边界检查不是必需的，而且我已经使它成为迭代而不是递归的。它返回范围[ min，max ]内的值，其中 max >= min和 1+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);
}
小开

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

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的长乘法来完成的。

When the number of bits is sufficiently large compared to n, the bias becomes immeasurably small.

如果 RAND_MAX + 1小于 n(如在 this question中) ，或者如果它不是2的幂并不重要，但是如果 RAND_MAX * n很大，则必须注意避免整数溢出。

小开

如前所述，模是不够的，因为它歪曲了分布。下面是我的代码，它掩盖了位，并使用它们来确保分布不被歪曲。

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


}

The following simple code lets you look at the distribution:

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


}
小开

虽然 Ryan 是正确的，但基于对随机性来源的了解，解决方案可以简单得多。重申这个问题:

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

根据我的经验，如果箱子(或“盒子”)的数量明显小于原始数字的范围，还有的原始来源是加密强大的-没有必要通过所有的繁文缛节，和简单的模除法将足够(如 output = rnd.next() % (rmax+1)，如 rmin == 0) ，并产生随机数均匀分布“足够”，没有任何损失的速度。关键因素是随机性来源(例如，孩子们，不要在家里尝试 rand())。

这里有一个例子/证明它在实践中是如何工作的。我希望生成从1到22的随机数，拥有一个加密强大的源，可以生成随机字节(基于 Intel 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 不支持这些新指令)。

小开

这里有一个比 Ryan Reich 的解决方案稍微简单一些的算法:

/// 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 = ((uint64_t)RAND_MAX + 1) - (((uint64_t)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
小开

为了避免模数偏差(建议在其他答案) ，你可以使用:

arc4random_uniform(MAX-MIN)+MIN

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

arc4random_uniform(20-10)+10


arc4random_uniform(10)+10

简单的解决方案，比使用“ rand ()% N”更好。

小开

将返回范围[0,1]内的浮点数:

#define rand01() (((double)random())/((double)(RAND_MAX)))

提交答案