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

How to generate a random integer number from within a range

提问by Jamie Keeling

This is a follow on from a previously posted question:

这是之前发布的问题的后续：

How to generate a random number in C?

如何在C中生成随机数？

I wish to be able to generate a random number from within a particular range, such as 1 to 6 to mimic the sides of a die.

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

How would I go about doing this?

我该怎么做呢？

回答by Ryan Reich

All the answers so far are mathematically wrong. Returning rand() % Ndoes not uniformly give a number in the range [0, N)unless Ndivides the length of the interval into which rand()returns (i.e. is a power of 2). Furthermore, one has no idea whether the moduli of rand()are independent: it's possible that they go 0, 1, 2, ..., which is uniform but not very random. The only assumption it seems reasonable to make is that rand()puts out a Poisson distribution: any two nonoverlapping subintervals of the same size are equally likely and independent. For a finite set of values, this implies a uniform distribution and also ensures that the values of rand()are nicely scattered.

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

This means that the only correct way of changing the range of rand()is to divide it into boxes; for example, if RAND_MAX == 11and you want a range of 1..6, you should assign {0,1}to 1, {2,3}to 2, and so on. These are disjoint, equally-sized intervals and thus are uniformly and independently distributed.

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

The suggestion to use floating-point division is mathematically plausible but suffers from rounding issues in principle. Perhaps doubleis high-enough precision to make it work; perhaps not. I don't know and I don't want to have to figure it out; in any case, the answer is system-dependent.

使用浮点除法的建议在数学上是合理的，但原则上存在舍入问题。也许double是足够高的精度使其工作；也许不是。我不知道，也不想弄清楚；无论如何，答案取决于系统。

The correct way is to use integer arithmetic. That is, you want something like the following:

正确的方法是使用整数算法。也就是说，您需要类似以下内容：

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

The loop is necessary to get a perfectly uniform distribution. For example, if you are given random numbers from 0 to 2 and you want only ones from 0 to 1, you just keep pulling until you don't get a 2; it's not hard to check that this gives 0 or 1 with equal probability. This method is also described in the link that nos gave in their answer, though coded differently. I'm using random()rather than rand()as it has a better distribution (as noted by the man page for rand()).

循环是获得完美均匀分布所必需的。例如，如果给你从 0 到 2 的随机数，而你只想要从 0 到 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 nbits (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 - 1in place of RAND_MAX) to pull a random value less than 2**n, assuming you have a numerical type that can hold such a value. Finally, of course, you can get values in [min, max]using min + random_at_most(max - min), including negative values.

如果您想获得默认范围之外的随机值[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，假设你有一个数值类型，它可以保持这样的一个值。最后，当然，您可以在[min, max]using 中获取值min + random_at_most(max - min)，包括负值。

回答by theJPster

Following on from @Ryan Reich's answer, I thought I'd offer my cleaned up version. The first bounds check isn't required given the second bounds check, and I've made it iterative rather than recursive. It returns values in the range [min, max], where max >= minand 1+max-min < RAND_MAX.

继@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);
}

回答by Sattar

Here is a formula if you know the max and min values of a range, and you want to generate numbers inclusive in between the range:

如果您知道某个范围的最大值和最小值，并且想要生成包含在该范围之间的数字，则可以使用以下公式：

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

回答by nos

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

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

See herefor other options.

请参阅此处了解其他选项。

回答by Armstrongest

Wouldn't you just do:

你不会只是做：

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

%is the modulus operator. Essentially it will just divide by 6 and return the remainder... from 0 - 5

%是模运算符。本质上它只会除以 6 并返回余数......从 0 - 5

回答by sh1

For those who understand the bias problem but can't stand the unpredictable run-time of rejection-based methods, this series produces a progressively less biased random integer in the [0, n-1]interval:

对于那些了解偏差问题但不能忍受基于拒绝的方法的不可预测的运行时间的人，这个系列在[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);
...

It does so by synthesising a high-precision fixed-point random number of i * log_2(RAND_MAX + 1)bits (where iis the number of iterations) and performing a long multiplication by n.

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

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

当位数与 相比足够大时n，偏差变得不可估量。

It does not matter if RAND_MAX + 1is less than n(as in this question), or if it is not a power of two, but care must be taken to avoid integer overflow if RAND_MAX * nis large.

如果RAND_MAX + 1小于n（如在这个问题中），或者它不是 2 的幂都没有关系，但是如果RAND_MAX * n很大，必须小心避免整数溢出。

回答by K. Biermann

Here is a slight simpler algorithm than Ryan Reich's solution:

这是一个比 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

回答by magamig

In order to avoid the modulo bias (suggested in other answers) you can always use:

为了避免模偏差（在其他答案中建议），您可以始终使用：

arc4random_uniform(MAX-MIN)+MIN

Where "MAX" is the upper bound and "MIN" is lower bound. For example, for numbers between 10 and 20:

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

arc4random_uniform(20-10)+10

arc4random_uniform(10)+10

Simple solution and better than using "rand() % N".

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

回答by Mouse

While Ryan is correct, the solution can be much simpler based on what is known about the source of the randomness. To re-state the problem:

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

• There is a source of randomness, outputting integer numbers in range [0, MAX)with uniform distribution.
• The goal is to produce uniformly distributed random integer numbers in range [rmin, rmax]where 0 <= rmin < rmax < MAX.

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

In my experience, if the number of bins (or "boxes") is significantly smaller than the range of the original numbers, andthe original source is cryptographically strong - there is no need to go through all that rigamarole, and simple modulo division would suffice (like output = rnd.next() % (rmax+1), if rmin == 0), and produce random numbers that are distributed uniformly "enough", and without any loss of speed. The key factor is the randomness source (i.e., kids, don't try this at home with rand()).

根据我的经验，如果垃圾箱（或“盒子”）的数量明显小于原始数字的范围，并且原始来源在密码学上很强 - 没有必要经历所有那些复杂的事情，简单的模除法会足够（如output = rnd.next() % (rmax+1), if rmin == 0），并产生均匀分布的随机数“足够”，并且没有任何速度损失。关键因素是随机性来源（即，孩子们，不要在家里尝试使用rand()）。

Here's an example/proof of how it works in practice. I wanted to generate random numbers from 1 to 22, having a cryptographically strong source that produced random bytes (based on Intel RDRAND). The results are:

这是它在实践中如何工作的示例/证明。我想生成从 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%

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%

This is as close to uniform as I need for my purpose (fair dice throw, generating cryptographically strong codebooks for WWII cipher machines such as http://users.telenet.be/d.rijmenants/en/kl-7sim.htm, etc). The output does not show any appreciable bias.

这与我的目的所需要的一样接近统一（公平掷骰子，为二战密码机生成强大的密码本，例如http://users.telenet.be/d.rijmenants/en/kl-7sim.htm等）。输出没有显示任何明显的偏差。

Here's the source of cryptographically strong (true) random number generator: Intel Digital Random Number Generatorand a sample code that produces 64-bit (unsigned) random numbers.

这是加密强（真）随机数生成器的来源： 英特尔数字随机数生成器和生成 64 位（无符号）随机数的示例代码。

int rdrand64_step(unsigned long long int *therand)
{
  unsigned long long int foo;
  int cf_error_status;

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

I compiled it on Mac OS X with clang-6.0.1 (straight), and with gcc-4.8.3 using "-Wa,q" flag (because GAS does not support these new instructions).

我在 Mac OS X 上使用 clang-6.0.1（直接）和 gcc-4.8.3 使用“-Wa,q”标志编译它（因为 GAS 不支持这些新指令）。

回答by Andrew Chambers

As said before modulo isn't sufficient because it skews the distribution. Heres my code which masks off bits and uses them to ensure the distribution isn't skewed.

如前所述，取模是不够的，因为它会扭曲分布。这是我的代码，它屏蔽了位并使用它们来确保分布不偏斜。

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

}