Go 语言实现线性同余发生器（LCG）算法

3. 周期条件（Hull–Dobell 定理）

LCG 想要达到最大周期 m，必须满足：

1. c 与 m 互质
2. a - 1 能被 m 的所有质因子整除
3. 若 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 := uint64(42)
    lcg := NewLCG(seed, a, c, m)
    fmt.Println("生成的伪随机数序列：")
    for i := 0; i < 10; i++ {
        fmt.Println(lcg.Next())
    }
    fmt.Println("生成 [10, 100) 范围内的随机数：")
    for i := 0; i < 5; i++ {
        fmt.Println(lcg.NextIntInRange(10, 100))
    }
}

代码解读

1. LCG 结构体

用于保存线性同余发生器的全部状态与参数，是算法的核心载体。

2. Next 方法

• 按照 LCG 公式生成下一个随机数
• 更新内部状态
• 确保序列连续、可复现

3. NextIntInRange 方法

• 将 LCG 输出映射到指定区间
• 用于模拟'实际可用的随机数'

4. main 方法

• 演示 LCG 的基本使用方式
• 验证序列的确定性与可重复性

总结

通过本项目，我们完整实现并理解了：

1. 伪随机数的本质：确定性递推
2. 线性同余发生器的数学结构
3. 参数选择对随机质量的巨大影响
4. 算法如何从数学公式落地为工程代码

LCG 的意义不在于'好不好用'，而在于：

它是理解所有现代随机数算法的起点

常见问题

Q1：LCG 是真随机吗？

不是，它是伪随机，完全可预测。

Q2：LCG 安全吗？

不安全，绝不能用于加密、安全、Token 等场景。

Q3：为什么很多语言早期都用 LCG？

因为：

• 实现极其简单
• 性能极高
• 在早期硬件条件下非常实用

Q4：LCG 最大的问题是什么？

• 低维分布差
• 周期有限
• 易被预测

扩展方向

1. 实现乘同余发生器（c = 0）
2. 对比 LCG 与 Xorshift、MT19937
3. 用统计方法分析随机质量
4. 实现跳跃（jump-ahead）算法
5. 封装为统一 PRNG 接口