c - rand() 示例代码，对大于最大值的不必要检查？

Question

我一直在调查 int rand()来自 <stdlib.h> 的函数在 C11 中，当我偶然发现以下 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
[...]

问题:

1. 为什么要添加+ 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] ?

2. 基于上一个问题，假设 [0,5] , 1 + (rand()/((RAND_MAX+1u)/6))应该只通过 [1,6]并且永远不会触发第二个循环？

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

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

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

Answer 1

代码通过确保 [1, 6] 中的每个可能结果都是来自 rand 的返回值数量完全相同的输出来避免偏差。 .

根据定义，rand返回 int值从 0 到 RAND_MAX .所以有1+RAND_MAX它可以返回的可能值。如果1+RAND_MAX不是6的倍数，那么不可能把它分成6个完全相等的整数区间。所以代码将它分成 6 个尽可能大的相等间隔和一个奇数大小的片段间隔。然后结果rand被映射到这些区间:前六个区间对应结果从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 个数字。在第七区间，可能的返回值在[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。值(value)观。

这是从 rand 生成均匀分布的最佳方式从某种意义上说，如果我们使用这样的方案，它的拒绝次数最少。¹ rand 的范围已被分成六个尽可能大的区间。剩余的零碎区间不能使用，因为余数 r 小于 6，所以 r 未使用的值不能平均分配给 x 的六个所需值.

脚注

¹ 这不一定是使用 rand 的最佳方式总体上在 [1, 6] 中生成随机数。例如，来自单个 rand用 RAND_MAX 打电话等于32767，我们可以把这个值看作一个从000000到411411的六进制数字。如果它小于400000，我们可以取最后五位，每个数字均匀分布在[0, 5]，并加上一个gts我们想要的 [1, 6]。如果在 [400000, 410000) 中，我们可以使用最后四位数字。如果在[410000, 411000)，我们可以用最后三个，以此类推。此外，否则会丢弃的信息(例如前导数字)可能会集中在多个 rand 上。调用以增加我们每次调用 rand 获得的平均输出数量.