<stdlib.h> rand() 示例代码，对大于最大值的不必要检查？

Question

我一直在研究 C11 中 <stdlib.h> 的 int rand() 函数，当我偶然发现以下 cppreference-example 用于滚动六面骰子时。

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
 
int main(void)
{
    srand(time(NULL)); // use current time as seed for random generator
    int random_variable = rand();
    printf("Random value on [0,%d]: %d\n", RAND_MAX, random_variable);
 
    // roll a 6-sided die 20 times
    for (int n=0; n != 20; ++n) {
        int x = 7;
        while(x > 6) 
            x = 1 + rand()/((RAND_MAX + 1u)/6); // Note: 1+rand()%6 is biased
        printf("%d ",  x); 
    }
}

具体这部分：

[...]
        while(x > 6) 
            x = 1 + rand()/((RAND_MAX + 1u)/6); // Note: 1+rand()%6 is biased
[...]

问题：

为什么要加+ 1u？因为 rand() 是 [0,RAND_MAX] 我猜那做 rand()/(RAND_MAX/6) -> [0,RAND_MAX/(RAND_MAX/6)] -> [0,6]？和因为它是整数除法 (LARGE/(LARGE+small)) < 1 -> 0，添加 1u 可以得到所需的范围 [0,5]?
基于上一个问题，假设 [0,5]，1 + (rand()/((RAND_MAX+1u)/6)) 应该只经过 [1,6] 而永远不会触发第二个循环？

一直在四处寻找 rand() 是否在某个时候返回了 float，但是这似乎是对旧代码的巨大破坏？我猜是支票如果您添加 1.0f 而不是 1u 使其成为浮点数，则有意义分配？

试图绕过这个，感觉我可能会失踪东西..

(P.s。这不是任何安全关键的基础，我只是在探索标准库。 D.s)

Answer 1

代码通过确保 [1, 6] 中的每个可能结果是来自 rand.

的 return 个值的输出完全相同来避免偏差

根据定义，rand returns int 值从 0 到 RAND_MAX。所以它可以 return 有 1+RAND_MAX 个可能的值。如果1+RAND_MAX不是6的倍数，那么不可能把它分成6个完全相等的整数区间。所以代码将它分成 6 个尽可能大的相等间隔和一个奇数大小的片段间隔。然后rand的结果映射到这些区间：前6个区间对应结果1到6，最后一个区间被拒绝，代码重试。

当我们将 1+RAND_MAX 除以 6 时，有一些商 q 和一些余数 r。现在考虑 rand() / q:

的结果

当rand产生一个数在[0,q−1]时，rand() / q将为0。
当rand在[q中产生一个数时，2q−1]，rand() / q将是 1.
当rand产生一个数在[2q, 3q−1], rand() / q将是 2.
当rand产生一个数在[3q, 4q−1], rand() / q将是 3.
当rand产生一个数在[4q, 5q−1], rand() / q将是 4.
当rand产生一个数在[5q, 6q−1], rand() / q将是 5.
当 rand 产生 6q 或更大的数字时，rand() / q 将为 6。

观察前六个区间中的每个区间，恰好有 q 个数字。在第七区间，可能的return值在[6q,RAND_MAX]中。该间隔包含 r 个数字。

此代码通过拒绝最后一个间隔来工作：

int x = 7;
while(x > 6) 
    x = 1 + rand()/((RAND_MAX + 1u)/6);

每当 rand 在最后一个片段间隔中生成一个数字时，此代码将拒绝它并重试。当 rand 在其中一个区间内生成一个数字时，此代码接受它并退出（在加 1 之后 x 中的结果是 1 到 6 而不是 0 到 5）。

因此，从 1 到 6（含）的每个输出都映射到完全相等数量的 rand 个值。

这是从 rand 产生均匀分布的最佳方式，因为它有最少的拒绝，因为我们正在使用这样的方案。¹ rand的范围被分成了六个区间，尽可能的大。剩余的零碎区间不能使用，因为余数r小于6，所以r未使用的值不能平分到6个想要的值x.

脚注

¹ 这不一定是使用 rand 在 [1, 6] 总体上生成随机数的最佳方法。例如，从 RAND_MAX 等于 32767 的单个 rand 调用中，我们可以将该值视为从 000000 到 411411 的六进制数字。如果小于 400000，我们可以取最后五个数字，每个数字均匀分布在 [0, 5] 中，并添加一个 gts 我们所需的 [1, 6]。如果在 [400000, 410000) 中，我们可以使用最后四位数字。如果在[410000, 411000)，我们可以用最后三个，以此类推。此外，其他被丢弃的信息，例如前导数字，可能会在多个 rand 调用中汇集，以增加我们每次调用 rand.

获得的平均输出数

<stdlib.h> rand() 示例代码，对大于最大值的不必要检查？

<stdlib.h> rand() example code, unnecessary check for larger than max?

c

random

c11

脚注