算法题做了一千道，不代表你真的会用算法。这是我近半年最深的体会。别误会，我不是劝你放弃刷题，而是想说：与其在在线评测系统上机械地记忆套路，不如抽一个周末，从零手写一个看起来没什么用、实际上能把好几个核心概念串在一起的小东西——伪随机数生成器。
为什么选伪随机数？因为它在概念上正好踩中三个高频考点：伪随机数生成本身就是一个递推过程，本质上和动态规划（DP）的状态转移同源；生成器的每一次输出都依赖内部状态，天然就是一个状态机；而想让生成器跑得快，又逃不开位运算和缓存优化。这三个词平时刷题时都是分开学的，但真实项目里它们永远缠在一起。这篇文章我会从算法选型讲起，把线性同余发生器（LCG）的参数怎么定、状态怎么封装、缓存怎么优化逐一拆开，代码全部是C语言，直接复制就能编译运行。适合准备面试、想理解算法本质、或者对系统库底层实现好奇的开发者，看完之后你能自己写一个合格的随机数生成器，还能顺手解释清楚DP、状态机、缓存优化到底在工程里长什么样。
1. 整体设计与思路拆解
1.1 为什么选伪随机数当“练手项目”
面试题里的算法往往都是单点知识：树的遍历考递归、排序考分治、最短路考图论，每道题练一个技能，彼此之间没有联系。但真实工程里没有“单点知识”，一个功能要同时牵扯数学、数据结构和硬件特性。
伪随机数生成器就是一个典型的“链路式”小系统。它看起来只有几行代码，实际拆开全是学问：
- 数学层面要理解模运算、同余、数论定理；
- 代码层面要设计状态结构、封装接口、控制副作用；
- 性能层面要关心取模运算的开销、内存访问模式、缓存命中率。
更重要的是，它是系统库里“最熟悉的陌生人”。我用过无数次的rand()、random()，但直到自己动手写了一个，才真正明白那个黑盒里到底发生了什么。对开发者来说，亲手揭开一个日常依赖的黑盒，带来的理解深度远超多刷几十道题型。
1.2 常见生成算法怎么选
种常见的伪随机数算法摆在一起对比过，各有各的脾气。
| 算法 | 周期 | 状态大小 | 实现难度 | 适合场景 |
|---|---|---|---|---|
| 线性同余（LCG） | 取决于模数 m | 8 字节 | 低 | 教学、嵌入式、快速模拟 |
| xorshift | 2^k - 1 | 16 字节 | 低 | 通用快速随机数 |
| 梅森旋转（MT19937） | 2^19937 - 1 | 约 2.5 KB | 高 | 科学计算、蒙特卡洛模拟 |
我最终选了 LCG，理由很直接：它的数学原理是可推导、可验证的，周期条件有严格的数论定理兜底，代码又短到不会喧宾夺主。我们这次的重点是理解 DP、状态机、缓存优化，而不是纠结复杂位操作。xorshift 其实也很有意思，但它把精力全放在位运算技巧上了，不适合当教学主线。梅森旋转质量最高，但 2.5KB 的状态本身就引入了一个复杂度，等把 LCG 吃透了再研究它不迟。
1.3 三个知识点的串联主线
这次动手要解决的三个知识点，全部挂在同一个生成器上：
- DP 视角：LCG 的递推方程
X(n+1) = (a * X(n) + c) mod m就是一个一维 DP 的状态转移方程，初值 X(0) 就是边界条件。如果再给递推加上记忆化，那就是教科书级别的自顶向下动态规划； - 状态机视角：生成器内部只维护一个可变状态，每次调用
next()本质都是一次状态迁移。如果再把生命周期（未初始化、可用、耗尽）也建模进去，就是一个显式有限状态机； - 缓存优化视角：取模运算慢，用位掩码代替；高频访问的状态变量要按缓存行对齐；预计算表可以把随机计算变成连续内存访问，这些都是真实场景里优化性能的典型手法。
这一套组合拳打下来，三个孤立的算法概念就串成了一条线。后面我会用三个版本的代码，把这条线一步一步走完。
2. 核心细节解析与实操要点
2.1 LCG 的数学原理与满周期条件
LCG 的公式是X(n+1) = (a * X(n) + c) mod m，其中：
m是模数，决定周期上界；a是乘数；c是增量；X(0)是种子。
如果参数选得不对，生成序列的周期会非常短，根本不够用。怎么选？有个叫 Hull-Dobell 定理的东西，给出了 LCG 达到满周期（周期等于 m）的充分必要条件：
c和m互质；a - 1能被m的所有质因数整除；- 如果
m能被 4 整除，那么a - 1也要能被 4 整除。
我当时用m = 2^32，想让周期达到完整的 2^32，也就是 42 亿多。然后选了一组经典的参数：a = 1664525，c = 1013904223。验算走一遍：
gcd(1013904223, 2^32) = 1，因为 2^32 的质因数只有 2，而 1013904223 是奇数，互质成立；a - 1 = 1664524，m的唯一质因数是 2，1664524 显然能被 2 整除；- 因为
m能被 4 整除，所以还要看1664524 / 4 = 416131，整除成立。
三个条件全部满足，周期就是 2^32。这个推导过程让我印象很深：以前在数据结构课上学到“参数不能随便选”的时候只觉得是老师吓唬人，直到自己验证了一遍，才算从根上明白“定理是拿来用的，不是拿来背的”。
2.2 为什么输出高位比低位更“随机”
LCG 有一个很坑的性质：当m = 2^32时，输出的低 k 位序列周期只有 2^k。换句话说，最低位的周期是 2，序列就是 0、1、0、1 交替，肉眼可见地荒谬。
我第一次测试时直接返回了state & 1，看到输出的序列我差点以为代码写错了。后来查资料才反应过来：不能贪图方便取低位，应该取高位。我在代码里用的是state >> 16，取高 16 位，这样序列的随机性明显好很多。如果只需要单字节，也可以(state >> 16) & 0xFF。
这个细节在真实项目里非常致命。如果一份模拟数据直接用了低位随机数，生成出来的“随机”事件可能呈现周期性规律，数据分析阶段根本查不出来。所以随机数生成器有一个基本原则：要尽量使用状态的高位输出。
2.3 用 DP 视角看递推与记忆化
LCG 的本质是一维递推，而一维递推就是 DP 的地基。如果我只想取第 N 个随机数，最朴素的做法是从种子里开始一步步推下去：
uint32_t rand_at(int n) { uint32_t state = seed; for (int i = 0; i < n; i++) { state = 1664525u * state + 1013904223u; } return state; }这个写法的问题是：如果业务里要反复查询“第 100 万个随机数”，每次查询都从种子重新算，复杂度是 O(N)，查询多了根本扛不住。解决办法就是记忆化——用一个数组把算过的值存下来：
#define MAX_N 1000000 static uint32_t memo[MAX_N + 1]; static int computed[MAX_N + 1]; uint32_t rand_at_memo(int n) { if (computed[n]) { return memo[n]; } if (n == 0) { computed[0] = 1; memo[0] = seed; return memo[0]; } memo[n] = 1664525u * rand_at_memo(n - 1) + 1013904223u; computed[n] = 1; return memo[n]; }有没有觉得这个结构很眼熟？这就是“带记忆化的递归”，也就是自顶向下的动态规划。memo数组是 DP 表，computed数组是状态是否已求解的标记，递归调用是在拆分子问题。如果继续把rand_at_memo(n-1)的递归改成循环自底向上填表，那就变成了最经典的 DP 写法。
我当时做完这个版本之后突然开窍了：面试里那些斐波那契、爬楼梯问题，跟这个随机数的记忆化在思想上完全相通。区别只是面试题把递推关系直接甩你脸上，而这里的递推关系藏在一个数学公式里。能把“隐藏的递推”识别出来，比背一百道模板题有用得多。
3. 实操过程与核心环节实现
3.1 基础版：8 行代码跑通 LCG
先上一个最干净的版本，把核心逻辑跑通：
#include <stdint.h> #include <stdio.h> typedef struct { uint32_t state; } lcg_t; void lcg_seed(lcg_t *rng, uint32_t seed) { rng->state = seed; } uint32_t lcg_next(lcg_t *rng) { rng->state = 1664525u * rng->state + 1013904223u; return rng->state >> 16; } int main() { lcg_t rng; lcg_seed(&rng, 2024); for (int i = 0; i < 10; i++) { printf("%u\n", lcg_next(&rng)); } return 0; }这里有几个细节值得展开：
- 用
uint32_t而不是int，是因为无符号整数在溢出时是明确定义的“回绕”，正好等价于模 2^32。用有符号int的话，溢出是未定义行为，编译器优化后可能出现意想不到的结果； - 乘法里写
1664525u而不是1664525，是为了强行使整个表达式按照无符号数运算； - 返回
state >> 16而不是直接返回state，就是刚才说的“取高位”原则。
编译命令是gcc -O2 -o lcg_basic lcg_basic.c。运行后能看到一组看似无序的数。到这一步，一个最小可用的随机数生成器就已经能工作了。
3.2 状态机封装：把“能跑”变成“能维护”
裸函数虽然能跑，但不好融入真实系统。真实系统里随机数生成器要能被创建、重置、查询状态，还要防止误用。我第二个版本把生命周期建模成了显式的状态机：
typedef enum { RNG_UNSEEDED, RNG_READY, RNG_DEPLETED } rng_phase_t; typedef struct { rng_phase_t phase; uint32_t state; uint32_t counter; uint32_t max_count; } rng_t; void rng_init(rng_t *rng, uint32_t seed, uint32_t max_count) { rng->phase = RNG_READY; rng->state = seed; rng->counter = 0; rng->max_count = max_count; } int rng_next(rng_t *rng, uint32_t *out) { if (rng->phase != RNG_READY) { return -1; } rng->state = 1664525u * rng->state + 1013904223u; *out = rng->state >> 16; rng->counter++; if (rng->counter >= rng->max_count) { rng->phase = RNG_DEPLETED; } return 0; } void rng_reset(rng_t *rng, uint32_t seed) { rng->phase = RNG_READY; rng->state = seed; rng->counter = 0; }这个封装的核心改动是引入了phase字段。有了它，未播种就调用next()会返回错误码，不会返回一个静默的错误结果；达到设定上限后会进入DEPLETED状态，提醒上层“该重置了”。状态的迁移关系非常清晰：
INIT → READY：调用rng_init或rng_reset；READY → DEPLETED：调用rng_next且counter达到上限；DEPLETED → READY：调用rng_reset。
这就是一个教科书级的有限状态机。平时刷题时写状态机都是把状态放在布尔变量里，翻来覆去也就两三个状态。这里的状态机加上了业务语义，代码不但好读，而且不容易被误用。
3.3 缓存优化与性能实测
基础版跑通之后，我开始琢磨性能。随机数生成最容易被性能拖后腿的地方有两个：取模运算和内存访问模式。
取模的优化很简单：因为模数是 2^32，所以x mod 2^32等价于x & 0xFFFFFFFF，而 C 语言里无符号整数溢出天然完成这个操作，不需要额外写。真正让性能有明显变化的是把“取高位”做一个显式的移位，再配合预计算表。
我加了一张 256 字节的置换表（S 盒），生成随机数时先做一次 LCG 递推，再从表里取一个预先算好的值做异或混合：
static uint8_t sbox[256]; void sbox_init(void) { for (int i = 0; i < 256; i++) { sbox[i] = (uint8_t)((i * 131 + 17) % 256); } } uint32_t lcg_next_fast(lcg_t *rng) { rng->state = 1664525u * rng->state + 1013904223u; uint32_t high = rng->state >> 24; return (rng->state ^ sbox[high]); }这种“查表混合”在密码学上叫白化（whitening），能打散 LCG 的低位结构。在性能上，它让每次生成随机数都会访问一次连续内存，只要表在 L1 缓存里，访问开销很小，但配合循环展开和对齐，整体吞吐量会有提升。
我还做了一个 1000 万次调用的性能测试，对比三个版本：
| 版本 | 耗时（近似） | 说明 |
|---|---|---|
| 基础版（取高位） | 120 ms | 纯算术，无额外内存访问 |
| S 盒混合版 | 95 ms | 多一次查表，但随机性更好 |
| S 盒 + 循环展开版 | 70 ms | 手动展开 4 次循环，减少分支开销 |
clock()计时的测试代码不复杂，核心就是把调用包在循环里累加结果，防止编译器把无副作用的调用优化掉。要提醒的是，这个数字在不同 CPU、不同编译器优化级别下会有差异，真正重要的是方法论：位运算替代除法、热点数据保持内存连续、循环展开减少控制流开销。
3.4 完整示例：用生成器模拟一次抽卡活动
光写生成器本身还有点纸上谈兵，我把它放进一个真实场景里跑了一遍：模拟抽卡概率验证。
假设某游戏抽卡，SSR 概率是 1.5%，普通物品概率是 98.5%。我用生成器产生 0 到 65535 之间的随机数，如果小于 983（对应 1.5%），就算抽中 SSR。连续模拟 100 万次，统计 SSR 出现的频率：
uint32_t threshold = 983; int ssr_count = 0; int total = 1000000; for (int i = 0; i < total; i++) { uint32_t r = lcg_next(&rng); if (r < threshold) { ssr_count++; } } printf("SSR rate: %.4f%%\n", ssr_count * 100.0 / total);我跑了三次，结果分别是 1.502%、1.497%、1.501%，和理论值非常接近。这个例子说明两件事：第一，正确实现的 LCG 在宏观统计上能支撑业务模拟；第二，伪随机数“伪”在序列可由种子完全重现，但统计性质可以做得接近真实随机。测试时把种子固定，就是可复现实验；换一个种子，就是另一组独立样本，这对数据分析场景极其重要。
4. 常见问题与排查技巧实录
4.1 生成序列周期太短，数据一眼就能看出规律
最常见的症状是随机数在低位呈现明显的 0、1 交替，或者周期短到几百个数就开始循环。
排查思路很简单，先检查你是不是直接返回了state本身或state & 1这类低位结果。我之前踩过这个坑，后来统一改成state >> 16就好了。如果取高位之后周期还是短，那就要怀疑参数问题了。可以用一个极小的模数做离线验证，比如m = 16，把参数代进去手推几步，看序列是否在 16 步内完整遍历。或者用 Floyd 判圈算法（快慢指针）检测循环周期，代码量不大，很有用。
4.2 每次程序启动生成的序列都一样，导致实验结果重复
这是伪随机数“伪”的代价：种子固定，序列就固定。业务场景里如果不想要确定性结果，就得让每次启动的种子不一样。
常见的错误做法是拿当前时间的秒数做种子。这在单线程下没问题，但并发场景会翻车。我之前做多线程模拟时，每个线程各自new一个生成器，种子都用当前秒数，结果两个线程在同一秒内启动，生成的序列完全一致，最后两批实验数据一模一样，排查了半天才发现。
后来我把生成器改成进程级单例，初始种子用系统熵（比如读取/dev/urandom或者高精度时钟的低位混合），之后每个线程的种子由单例通过原子操作递增派生，彻底避免重复序列。这个教训的核心是：种子的来源和分发也是系统设计的一部分，不能随手一拍。
4.3 加了缓存优化反而变慢
S 盒不是越大越好。如果预计算表超过了 CPU 的 L1 缓存大小（通常 32KB 到 1MB），每次查表都会带来缓存未命中，性能会断崖式下跌。我试过把 S 盒扩大到 4MB，随机性好了一些，但速度比基础版还慢。后来明白了：查表优化要保证“表能住进缓存”，否则就是负优化。
另外，做性能对比时一定要开编译优化。-O0和-O2的差距非常大，不开优化谈“优化技巧”没有意义。我习惯用gcc -O2 -march=native做基准测试，这样比较能反映真实水平。
4.4 线程安全：共享生成器导致的序列异常
一个生成器实例如果被多个线程同时调用，rng->state = ...这个读改写操作会产生数据竞争，生成结果会错乱。最稳妥的解决方法是每个线程持有独立实例，或者用原子操作/互斥锁保护状态更新。如果只是追求吞吐量，线程本地存储是更好的选择——把生成器放到线程局部变量里，各用各的状态，既隔离了竞争，也保住了缓存局部性。
回看整个过程，我最大的感受是：很多算法概念，刷题时觉得抽象，是因为它们都被封装成了“已知条件”。而手搓一个伪随机数生成器，逼着你自己去发现递推关系、设计状态流转、优化内存访问，所有概念都落到了一行行能跑、能测、能比较的代码里。如果你也对这种“用一个小项目吃透多个概念”的方式感兴趣，我建议你找一个类似的小而精的系统——哈希表、缓存淘汰策略、布隆过滤器都行——亲手实现一遍。做完之后，你在面试里讲那些算法时的底气，会和现在完全不同。
