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

Question

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

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

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

我该如何实现呢？

- Jamie Keeling

---

如果你看一下你所提到的问题的第二个答案，你就能找到答案了。rand() % 6. - Mats Fredriksson

我不理解它是如何工作的，因此我决定提出一个单独的问题以获得清晰度。 - Jamie Keeling

随机想法：如果你对一群程序员进行随机抽样调查，你会发现其中有随机数量的人正在随机地思考如何随机生成数字。考虑到宇宙受到精确和可预测的定律支配，我们试图更随机地生成事物不是很有趣吗？这样的问题总是会引出超过10k个帖子的讨论。 - Armstrongest

@Mats rand() % 6 可能返回0。对于骰子来说不好。 - new123456

你能否将https://dev59.com/VHE85IYBdhLWcg3w_I78#6852396标记为被接受的答案，而不是链接到它的答案 :) 谢谢。 - Kev

Answer 1

到目前为止，所有的答案在数学上都是错的。如果 N 不能被 rand() 返回的区间长度整除（即是 2 的幂），那么返回 rand() % N 不会均匀地给出在范围 [0, N) 中的数字。此外，人们不知道 rand() 的模数是否独立：它们可能是 0, 1, 2, ...，这是均匀但不太随机的。唯一似乎合理的假设是 rand() 产生 Poisson 分布：相同大小的任意两个不重叠子区间等可能且独立。对于有限的值集，这意味着均匀分布，也确保了 rand() 的值被良好地散布。

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

使用浮点除法的建议在数学上是可行的，但原则上存在舍入问题。也许双精度是足够高精度的，可以使其工作；也许不是。我不知道，也不想去弄清楚；在任何情况下，答案是系统相关的。

正确的方法是使用整数算术。也就是说，您需要像以下这样的东西：

#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提供的链接中描述了。我使用random()而不是rand()，因为它有更好的分布（正如rand()的手册所指出的）。

如果您想获取默认范围之外的随机值[0，RAND_MAX]，那么您必须做一些巧妙的事情。也许最方便的方法是定义一个函数random_extended()，使用random_at_most()来拉取n位并返回[0，2 ** n)，然后将random_extended()代替random()使用random_at_most()（并将2 ** n - 1代替RAND_MAX）来拉取小于2 ** n的随机值，假设您有一个可以保存这样的值的数值类型。最后，当然，您可以使用min + random_at_most(max - min)，包括负值，来获得[min，max]中的值。

- Ryan Reich

---

进一步审查后，另一个问题是当 max - min > RAND_MAX 时，这种方法将无法正常工作，这比我之前提到的问题更为严重（例如 VC++ 的 RAND_MAX 只有32767）。 - interjay

我已经编辑了我的答案，以反映我多年来收到的一些评论！ - Ryan Reich

while循环可以更易读。与其在条件中执行赋值，您可能想要使用do {} while()。 - theJPster

好的，我会尽力进行翻译。以下是需要翻译的内容：“嘿，这个答案是Comet OS书中引用的 ;) 我第一次在教科书中看到这个。” - vpuente

这个也被引用在 OSTEP 的书里 :) http://pages.cs.wisc.edu/~remzi/OSTEP/ （第 9 章，第 4 页）。 - rafascar

Answer 2

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

- theJPster

---

注意，如果range >= RAND_MAX，这将会陷入无限循环。问我怎么知道的:/ - theJPster

请注意，您正在将int与unsigned int进行比较（r >= limit）。问题很容易通过将“limit”设置为int（可选地也包括“bucket”）来解决，因为RAND_MAX / range < INT_MAX且buckets * range <= RAND_MAX。编辑：我已经提交了编辑建议。 - rrrrrrrrrrrrrrrr

@Ryan Reich的解决方案仍然给了我更好（更少偏差）的分布。 - Vladimir

Answer 3

如果你知道一个范围的最大和最小值，且想要生成包含在该范围内的数值，那么可以使用以下公式：

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

- Sattar

---

正如Ryan的回答所指出的，这会产生偏见结果。 - David Wolever

结果存在偏见，对于 max+1-min 可能会发生 int 溢出。 - chux - Reinstate Monica

这只适用于整数最小值和最大值。如果最小值和最大值是浮点数，则无法执行％操作。 - Francesco Taioli

Answer 4

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

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

查看这里以获取其他选项。

- nos

---

@S.Lott - 不完全是这样。每个方法只是以略微不同的方式分配高概率情况。双倍数学运算给人的印象是那里有更多的精度，但你也可以轻松地使用 (((max-min+1)*rand())/RAND_MAX)+min 并获得可能完全相同的分布（假设 RAND_MAX 相对于 int 足够小而不会溢出）。 - user180247

这有些危险：如果rand()等于RAND_MAX，或者rand()非常接近RAND_MAX而浮点误差将最终结果推到max+1，那么它可能会（非常少见地）返回max+1。为了安全起见，在返回结果之前，您应该检查结果是否在范围内。 - Mark Dickinson

@Christoph: 我同意关于RAND_MAX + 1.0的说法。然而，我仍不确定这是否足以避免max + 1的返回：特别是最后的+ min涉及舍入，可能会在rand()的大值产生max + 1。完全放弃这种方法，使用整数算术更为安全。 - Mark Dickinson

如果像Christoph建议的那样，将RAND_MAX替换为RAND_MAX + 1.0，我认为只要使用整数算术来执行 + min，就是安全的：return (unsigned int)((max - min + 1) * scaled) + min。这个（不显然的）原因是，在假定IEEE 754算术和四舍六入的情况下（并且也假设max-min+1可以被一个双精度表示，但在一台典型的机器上这通常成立），对于任何正的双精度x和任何满足0.0 <= scaled && scaled < 1.0的双精度scaled，总是成立 x * scaled < x。 - Mark Dickinson

randr(0, UINT_MAX) 失败：总是生成 0。 - chux - Reinstate Monica

Answer 5

那么你就可以这样做：

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

%是模数运算符。它会将数字除以6并返回余数...从0-5。

- Armstrongest

---

它将给出1-6的结果。这就是+1的作用。 - Armstrongest

Simon，请给我展示一下任何使用rand()函数的libc库，其中包含生成器状态的低位（如果它使用LCG）。到目前为止，我还没有看到过这样的库——所有这些库（是的，包括MSVC并且RAND_MAX只有32767）都会移除低位。使用取模运算不是推荐的方法，因为它会导致分布偏向于较小的数字。 - Joey

@Johannes：也许现在不是什么问题，但传统上不建议使用低位。http://c-faq.com/lib/randrange.html - jamesdlin

@James: 对于 LCG 和一些其他生成器，我同意。然而，这只会成为一个问题，如果你是自己实现 PRNG，因为到目前为止，我看到的每个库和框架都替你屏蔽了这个问题。注意，还有一些生成器会产生低质量的高阶位。由于C甚至没有指定使用哪种PRNG，在盲目推荐丢弃低阶位方面没有太大作用。 - Joey

@Joey，NetBSD和glibc（对于TYPE_0）都使用其LCG的低位比特。 - sh1

Answer 6

对于那些了解偏差问题但无法忍受基于拒绝方法的不可预测运行时间的人来说，此系列在[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 进行长乘法运算来实现。当比特数与 n 相比足够大时，偏差变得微不足道。无论 RAND_MAX + 1 是否小于 n（如在此问题中），或者它是否是2的幂，都没有关系，但如果 RAND_MAX * n 很大，则必须注意避免整数溢出。

- sh1

---

“RAND_MAX”通常是“INT_MAX”，因此“RAND_MAX + 1”--> UB（就像INT_MIN一样） - chux - Reinstate Monica

@chux，这就是我所说的“如果RAND_MAX * n很大，则必须小心避免整数溢出”。您需要安排使用适当类型来满足您的要求。 - sh1

今天我测试了两个32位的int编译器，发现其中一个的RAND_MAX == 32767，而另一个则是RAND_MAX == 2147483647。我的总体经验（几十年）是RAND_MAX == INT_MAX更为常见。因此，我不同意合理的现代32位架构一定会有一个RAND_MAX在2^16 / 2。由于C规范允许32767 <= RAND_MAX <= INT_MAX，所以我仍然按照这个范围编码，而不是趋势。 - chux - Reinstate Monica

@cat 同一台64位电脑上：Visual Studio 2010 RAND_MAX == 32767 和 gcc-4.9.3-1.i686 RAND_MAX == 2147483647。 - chux - Reinstate Monica

仍然受到“必须小心避免整数溢出”的限制。 - sh1

Answer 7

以下是比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

- K. Biermann

---

RAND_MAX + 1 can readily overflow int addition. In that case, (RAND_MAX + 1) % range will generate questionable results. Consider (RAND_MAX + (uint32_t)1) - chux - Reinstate Monica

Answer 8

为了避免模数偏差（建议参考其他答案），您可以始终使用以下方法：

arc4random_uniform(MAX-MIN)+MIN

"MAX"代表上限，"MIN"代表下限。例如，对于介于10和20之间的数字：

arc4random_uniform(20-10)+10

arc4random_uniform(10)+10

这是一个比使用 "rand() % N" 更好的简单解决方案。

- magamig

---

哇喔，这比其他答案好了十亿倍。需要注意的是你首先需要 #include <bsd/stdlib.h>。还有，你知道如何在Windows上获得此功能而无需使用MinGW或CygWin吗？ - cat

不，它本身并不比其他答案更好，因为其他答案更通用。在这里，您只限于arc4random，而其他答案允许您选择不同的随机源，使用不同的数字类型...最后但并非最不重要的是，它们可能帮助某人理解问题。 不要忘记，这个问题对于其他可能具有特殊要求或无法访问arc4random的人也很有趣... 尽管如此，如果您可以访问它并需要快速解决方案，它确实是一个非常好的答案。 - K. Biermann

Answer 9

虽然Ryan是正确的，但解决方法可以更简单，基于有关随机源的已知信息。重新陈述问题：

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

根据我的经验，如果箱子（或“盒子”）数量显着小于原始数字的范围，并且原始源具有加密强度，则没有必要进行所有那些繁琐的步骤，简单的模除就足够了（例如output = rnd.next() % (rmax+1)，如果rmin == 0），并产生分布“足够”均匀的随机数，而且速度不会有任何损失。关键因素是随机性源（即，孩子们，在家里不要尝试使用rand()）。

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

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

- Mouse

---

使用gcc randu.c -o randu -Wa,q（Ubuntu 16上的GCC 5.3.1）或clang randu.c -o randu（Clang 3.8.0）编译可以通过，但在运行时会出现“非法指令(core dumped)”错误。有什么想法吗？ - cat

首先，我不知道你的CPU是否实际支持RDRAND指令。你的操作系统相当新，但CPU可能不是。其次（但这种情况不太可能）- 我不知道Ubuntu包含哪种汇编程序（而且Ubuntu在更新软件包方面往往比较落后）。请查看我提到的英特尔网站以了解如何测试您的CPU是否支持RDRAND。 - Mouse

你确实提出了很好的观点。但我仍然不明白为什么rand()有那么大的问题。我进行了一些测试并发布了这个问题，但我还没有找到一个明确的答案。 - myradio

Answer 10

如前所述，模除不足以满足需求，因为它会扭曲分布。这是我的代码，它屏蔽位并使用它们来确保分布不会偏斜。

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

}

- Andrew Chambers

---

当您从rand()中拒绝数字时，效率会变得非常低。当范围的大小可以写成2^k + 1时，这将特别低效。然后，通过慢速rand()调用，将有近一半的尝试被条件拒绝。也许更好的方法是计算RAND_MAX模范围。例如: v = rand(); if (v > RAND_MAX - (RAND_MAX % range) -> reject and try again; else return v % range; 我知道取模是比掩码操作要慢得多的，但我仍然认为.....应该进行测试。 - Øystein Schønning-Johansen

rand() 返回一个在 [0..RAND_MAX] 范围内的 int。该范围可以很容易地成为 uint32_t 的子范围，然后 randomInRange(0, b) 不会生成 (INT_MAX...b] 范围内的值。 - chux - Reinstate Monica