背景
在计算机科学中，随机数是一个看似简单、却极其基础且重要的概念。
在现实世界中，随机性来源于物理过程（噪声、量子现象等），但在计算机中：
绝大多数所谓的'随机数'，其实都是'伪随机数'
也就是说，它们是通过确定性的数学公式生成的，只是'看起来像随机'。
在所有伪随机数生成算法中，Linear Congruential Generator（LCG，线性同余发生器）是：
- 历史最悠久
- 结构最简单
- 数学形式最清晰
- 教学中最常见
的一类算法。
LCG 早在 1950 年代就被提出，并长期作为：
- C 语言 rand() 的实现基础
- 教材中的随机数生成示例
- 嵌入式系统、早期操作系统的默认 PRNG
尽管在现代安全或高质量随机场景中，LCG 已不再推荐，但它在理解随机数生成原理、数论与工程实现之间的关系方面，仍然具有不可替代的教学价值。
因此，用 Go 语言实现 LCG，是一个非常适合算法教学、原理讲解、工程对照的经典项目。
需求
本项目的目标是：
使用 Go 语言完整实现一个 Linear Congruential Generator（线性同余发生器），并生成可重复的伪随机数序列。
具体需求如下：
1. 功能需求
- 实现标准 LCG 递推公式
- 支持自定义参数：模数 m、乘数 a、增量 c、初始种子 seed
- 可连续生成随机数序列
- 支持生成指定范围内的随机数
2. 算法要求
- 严格遵循 LCG 数学定义
- 所有计算使用整数运算
- 不依赖 Go 内置 math/rand
3. 工程要求
- 结构清晰，便于封装
- 状态可控，可复现
- 代码注释完整，适合教学
4. 教学要求
- 明确解释公式中每个参数的意义
- 说明 LCG 的周期问题
- 指出该算法的优缺点与适用场景
技术原理
1. 线性同余发生器的数学定义
LCG 的核心递推公式为：
Xₙ₊₁ = (a · Xₙ + c) mod m
其中：
- Xₙ：当前随机数
- Xₙ₊₁：下一个随机数
- m：模数（决定周期上限）
- a：乘数
- c：增量
- X₀：初始种子（seed）
所有'随机性'的来源，完全来自这一个公式。
2. 参数的数学意义
（1）模数 m
- 决定随机数取值范围：[0, m)
- 决定最大周期长度（理论上 ≤ m）
（2）乘数 a
- 决定序列的'扩散性'
- 不合理的 a 会导致序列规律明显
（3）增量 c
- 若 c = 0，称为乘同余发生器
- 若 c ≠ 0，称为混合同余发生器
- c 的存在有助于避免退化
（4）种子 seed
- 决定整个随机序列
- 相同参数 + 相同 seed ⇒ 完全相同的序列
3. 周期条件（Hull–Dobell 定理）
LCG 想要达到最大周期 m，必须满足：
- c 与 m 互质
- a - 1 能被 m 的所有质因子整除
- 若 m 是 4 的倍数，则 a - 1 也是 4 的倍数
这也是很多'坏随机数'的根源所在。
实现思路
本项目的实现思路如下：
1. 抽象一个 LCG 结构体
用于保存：
- 当前状态（current）
- 参数（a, c, m）
2. 提供 Next 方法
- 根据递推公式生成下一个随机数
- 更新内部状态
- 返回生成结果
3. 提供范围随机数方法
- 将 [0, m) 映射到 [min, max)
- 用于更贴近实际使用场景
4. 保证可复现性
- 不依赖系统时间
- 种子由用户显式指定
代码实现
// ==========================================
// 文件名：lcg.go
// 功能：Linear Congruential Generator（线性同余发生器）
// ==========================================
package main
import "fmt"
// LCG 表示一个线性同余随机数发生器
type LCG struct {
a uint64 // 乘数
c uint64 // 增量
m uint64 // 模数
current uint64 // 当前状态
}
// NewLCG 创建一个新的 LCG 实例
func NewLCG(seed, a, c, m uint64) *LCG {
return &LCG{
a: a,
c: c,
m: m,
current: seed,
}
}
// Next 生成下一个伪随机数
func (l *LCG) Next() uint64 {
l.current = (l.a*l.current + l.c) % l.m
return l.current
}
// NextIntInRange 生成指定区间 [min, max) 的随机整数
func (l *LCG) NextIntInRange(min, max uint64) uint64 {
if max <= min {
return min
}
return min + l.Next()%(max-min)
}
func main() {
// 一组经典 LCG 参数（类似 glibc 早期实现）
const (
m = 1 << 31
a = 1103515245
c = 12345
)
seed := ()
lcg := NewLCG(seed, a, c, m)
fmt.Println()
i := ; i < ; i++ {
fmt.Println(lcg.Next())
}
fmt.Println()
i := ; i < ; i++ {
fmt.Println(lcg.NextIntInRange(, ))
}
}
代码解读
1. LCG 结构体
用于保存线性同余发生器的全部状态与参数，是算法的核心载体。
2. Next 方法
- 按照 LCG 公式生成下一个随机数
- 更新内部状态
- 确保序列连续、可复现
3. NextIntInRange 方法
- 将 LCG 输出映射到指定区间
- 用于模拟'实际可用的随机数'
4. main 方法
- 演示 LCG 的基本使用方式
- 验证序列的确定性与可重复性
总结
通过本项目，我们完整实现并理解了：
- 伪随机数的本质：确定性递推
- 线性同余发生器的数学结构
- 参数选择对随机质量的巨大影响
- 算法如何从数学公式落地为工程代码
LCG 的意义不在于'好不好用'，而在于：
它是理解所有现代随机数算法的起点
常见问题
Q1：LCG 是真随机吗？
不是，它是伪随机，完全可预测。
Q2：LCG 安全吗？
不安全，绝不能用于加密、安全、Token 等场景。
Q3：为什么很多语言早期都用 LCG？
因为：
- 实现极其简单
- 性能极高
- 在早期硬件条件下非常实用
Q4：LCG 最大的问题是什么？
- 低维分布差
- 周期有限
- 易被预测
扩展方向
- 实现乘同余发生器（c = 0）
- 对比 LCG 与 Xorshift、MT19937
- 用统计方法分析随机质量
- 实现跳跃（jump-ahead）算法
- 封装为统一 PRNG 接口
