小范围随机数生成大范围采样

随机数生成器的扩展

题目：

已知一个函数 rand3()，能够等概率地生成整数 1, 2, 3。 现有一个包含 $N$ 个样本的数组 samples（$N > 3$）。 请利用 rand3() 实现一个函数，能够等概率地（即概率为 $1/N$）从这批样本中抽取一个元素。

我不知道有没有人的第一反应和我一样：数次生成随机数，然后直接相加。但这样毫无疑问是错了，这样会产生一个正态分布，而题目要求的是均匀分布。

实际的解决方案是使用进制思想，也就是将 rand3() 看作三进制的一个数：

公式：$val+=(rand3()-1)*(3^i)$

• 第一次 rand3() 决定高位（0, 1, 2）
• 第二次 rand3() 决定低位（0, 1, 2）
• 结果范围是 $0 \sim 8$（共9个数），且每个数出现的概率都是 $1/9$，这是均匀的。

当然，我们可以进一步使用秦九韶算法以加速计算：

在计算机科学中，它最常见的应用场景就是进制转换（比如将字符串 "123" 转为整数 123，或者将 3 进制转为 10 进制）。

秦九韶/霍纳发现，我们可以通过不断提取公因式 $x$ 来重写公式：

$$ \begin{aligned} P(x) &= 2x^2 + 1x + 2 \ &= (2x + 1)x + 2 \end{aligned} $$

如果是更高阶的，比如 $4x^3 + 3x^2 + 2x + 1$： $$ \begin{aligned} P(x) &= 4x^3 + 3x^2 + 2x + 1 \ &= (4x^2 + 3x + 2)x + 1 \ &= ((4x + 3)x + 2)x + 1 \end{aligned} $$

核心规律： $$NextValue = CurrentValue \times Base + Digit$$

在实际开发中，秦九韶算法有两个巨大的优势：

1. 避免了浮点运算 (math.Pow)
   • 计算机里的整数乘法 (*) 和加法 (+) 极快。
   • math.Pow 是浮点运算，速度慢，且在处理大整数时会有精度丢失（例如 pow(3, 10) 可能会算出 59048.99999，转 int 变成 59048 就错了）。
2. 符合数据流方向
   • 当我们生成随机数或者读取字符串时，通常是从左到右（高位到低位）读取的。
   • 普通幂累加法：需要先知道总共有多少位（算 $i$），或者要把数组倒过来从低位算起。
   • 秦九韶法：来一个数字处理一个，不需要预先知道总长度，非常适合流式处理（Stream）。

$$val=val*3+(rand3-1)$$

综上，golang 版本的 $[1,3]$ 随机数扩展至 100 可以写为：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

func rand3To100() int {
	// 定义一个只能生成[1,3]的随机数函数
	rand3 := func() int {
		return rand.Intn(3) + 1
	}

	// 最大随机数取值
	k := 100

	val := 0
	for {
		for range 5 {
			val = val*3 + rand3() - 1
		}
		if val <= k {
			break
		} else {
			val = 0
		}
	}
	return val
}