随机数生成问题

C 语言中的 rand() 函数

rand() 函数可以生成 [0, RAND_MAX] 范围内的随机整数，RAND_MAX 通常为 int 类型的最大值，C 规范要求它不能小于 32767。

如何得到 [ 1, n ] 的随机整数

一个简单的实现如下：

int n = 6;            //例如我想要 [1, 6] 的随机数
srand(time(NULL));
int random = 1 + rand() % 6;

我们可以很自然地想到利用取模运算得到 [0, 5] 的随机数，然后将结果加1得到 [1, 6] 的随机数，这也是笔者在中文互联网上搜索得到的几乎全部的答案。然而，在查看 C 参考手册 rand() 函数部分时，却发现官方示例代码如下：

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

官方示例代码为投掷一个 6 面骰子 20 次的结果，在生成 [1, 6] 的随机数部分的实现却截然不同，并且提示： 1+rand()%6 is biased，认为像上面那种简单的实现是有偏差的。

为什么 1 + rand() % 6 是有偏差的

首先众所周知的是 rand() 函数并不能给出真正意义上的随机数，在 rand() 函数的实现中，每给定一个唯一确定的种子(srand(seed))时，rand() 函数就会得到一个唯一确定与之对应的整数序列。也因此官方参考中也说明了不要将此函数应用于严肃的场景，例如加密。但是这个问题并不是真正导致上述方法产生偏差的原因。即使 rand() 函数能给出真正的随机数， 1 + rand() % 6 也是不正确的。这里真正的问题在于 rand() % 6，也就是取模运算，+ 1并没有影响。

来看一个极端的例子：假设 RAND_MAX = 10， 就是说 rand() 函数能够产生 [0, 10] 的随机数，现在我想要 [ 1, 3 ] 的随机数，使用 1 + rand() % 3 来产生我们想要的结果，那么对于 rand() 可能的结果 [0,1,2,3,4,5,6,7,8,9,10]，rand() % 3 得到的结果为 [ [0,1,2], [0,1,2], [0,1,2], [0, 1] ]，聪明的你现在已经看出问题了，没错，在 rand() % 3 的结果序列中 0, 1, 2 的数量并不相等，也就意味着 产生0, 1, 2 的概率并不相等，这与 rand() 的真随机与否无关。

如何正确实现

因此，应当保证 rand() % n 的结果中 [0, n-1] 范围内各个整数的数量相等才是正确的实现。我们可以通过限制 rand() 结果的上限来实现，也就是将其限制在 RAND_MAX范围内 n 的最大倍数内。在官方实现中是这样的：

x = 1 + rand()/((RAND_MAX + 1u)/6);

这里 RAND_MAX + 1u 将结果转为无符号型来避免 int 类型溢出。

另一种实现如下(参考stackoverflow)：

int MAX =  6 * ((RAND_MAX + 1u)/6);
int rand;
while (rand() >= MAX) {
    rand = rand();
}

参考资料：[https://stackoverflow.com/questions/49878942/why-is-rand6-biased]