如何正确使用随机数（如何生成随机数）

作者：marinewu，腾讯PCG客户端开发工程师

| 导语本文借 2022 年 8 月 Readability Golang 考试代码，讲解在使用随机数的常见陷阱和解决方案。内容主要以 Go 的标准库进行讲解，但问题与语言无关。

问题

以下是 8 月 Golang 的考试代码片段。该代码在使用随机数时存在哪些问题？

// ShouldTurnOn 被调用时会进行判定，按 Config.EnableProbability% 的概率返回真 func ShouldTurnOn() bool { rand.Seed(time.Now().UnixNano()) randNum := rand.Uint64() % 100 return randNum <= config.EnableProbability }概率非一致分布 Non-Uniform distribution

经典错误：通过取余操作对离散一致分布间做映射时，因为不能除尽导致偏移，不构成一致分布。

业务场景通常需要获取 [0, M) 的一致分布。但大部分随机数生成器都是在 2 的整数次幂上，即 [0, 1 << x) 的一致分布。我们通常希望通过某些简单的算术规则将 [0, 1 << x) 的一致分布映射至 [0, M) 的一致分布。

非常常见的做法是样例中的取余，如 rand() % 100，获得 [0, 100) 的一致分布。这样非常简单直观，但是，有缺陷。

简单的数论知识告诉我们 2 的幂永远无法被 100 除尽，因此，rand() 的一致分布的所有值无法被均匀分配到 [0, 100) 这 100 个桶中。这使得前几个桶被分配的概率会比后面的桶高。当 rand() 的取值范围很大，如 [0, 1 << 64) 时，影响较小。但是这仍然是一个 bug，尤其在原分布的桶较小时，如原分布是 [0, 32767) 时，影响更大。

因此，当我们希望从 [0, M) 的一致分布生成 [0, N) 的一致分布时，要小心概率偏移。一个正确的处理方案是：

当 M > N 时：

截取 [0, M) 中的部分分布 [0, M')，M' 是小于 M 且能被 N 除尽的最大值。它仍然是一个一致分布。
就 [0, M') 的生成随机数对 N 取模，即可保证生成 [0, N) 的一致分0905布。
当 M 能被 N 整除时，可以直接取余。

伪代码如下：

// randN returns a normally distributed result from [0, N) // It uses a normally distributed random number generator [0, M) func randN() int { max = M / N * N ( m = randM() if m >= max { // If m >= max, the nubmer is out of the distribution [0, max). Just throw away. return randN() } // Otherwise, just return the remainder. return m % N }

这段代码递归深度期望接近 1。具体期望计算与文末的扩展阅读的面试题相关。

当 M < N 时，一个可选的方案是：

通过取 t 次 M 值，直到 M ** t > N，以此生成一个 [0, M ** t) 的一致分布
以下处理同 M > N

上述方案正是 Go 的 rand 标准库的 rand.Int63n(int) 等提供 Uniform Distribution 方法的实现原理：Go Rand 实现

差一错误 Off-By-One Error

There are two hard things in computer science: cache invalidation, naming things, and off-by-one errors.

--Jeff Atwood

经典错误：边界处理失误，导致实际阈值比预期大 1%

注意返回的一致性分布是 [-0, 100)，也就是 0, 1, 2, ..., 99 的均匀分布。例如，当使用

return randNum <= 80

实际上有 81 个值 (0, 1, ..., 80）会被包含。这使得实际的概率为 81%。

一定要注意 off-by-one error。这种错误在线上难以察觉，但是在统计意义上会对业务造成明显影响。

Off-By-One 是隐蔽又容易出错的问题，在离散分布里，一定要注意区间的开闭。

当需要一个 [a, b] 的离散一致性分布时，其与 [a, b 1) 等价。因此，使用标准库时，应该先获取一个 [0, b - a 1) 的一致分布，然后映射到 [a, b]。即：

Uniform [a, b] == Uniform [a, b 1) == Uniform [0, b 1 - a) a性能、正确、安全

经典错误：频繁 Seed。

我们平时使用的大部分随机数是伪随机数，即算术生成随机数。它的原理是通过算术运算，迭代地生成一系列统计上均匀分布的结果。即，随机数的序列是：

rand(Seed), rand(rand(Seed)), rand(rand(rand(Seed))), ...

当调用 rand 后，生成的随机数会作为新的种子。因此，正常情况下，不需要每次调用 rand 前都初始化种子。样例的代码使用时间作为初始化种子，这样做会有几个可能的问题：

time.Now() 并不廉价。频繁获取时间是无谓的性能损耗。
重置随机数种子并没有必要。本质上，这相当于不再使用 rand 生成的随机数，而是使用时间作为随机数。如果在同一纳秒内调用这个方法，会产生完全一样的随机数。

因此，只要在 main() 或者在 init() 函数中初始化一次即可。如果不介意每次的随机数序列提确定性的，也可以跳过初始化 Seed。

rand.Seed 和取随机数的方法是线程安全的，但是这可能会导致性能问题。当需要高频大量生成随机数时，可能会造成大量的锁竞争。因此，应该使用新的 Source，如：

rand.New(rand.NewSource(seed)) // Caution: not thread-safe!

但是要注意，NewSource 默认是并发不安全的，因此，不要在协程/线程之间共享 NewSource 所产生的 Source。

另外，注意 rand 包是密码学不安全的。换言之，可能会被攻击者利用，即攻击者可能会根据生成的随机数的特征预测随机数。因此永远不要使用 rand 进行一些敏感随机数的生成。如果需要防攻击的随机数生成器，使用 crypto.rand(rand package - crypto/rand - Go Packages)

改进

经过以上的分析，代码改进如下：

// ShouldTurnOn 被调用时会进行判定，按 Config.EnableProbability% 的概率返回真 func ShouldTurnOn() bool { return rand.int(100) -> rand.Intn(100) < ...config.EnableProbability }进一步阅读