算法与理论计算机2020arxiv.org
是时候放弃 Mersenne Twister 了（2019）
It is high time we let go of the Mersenne Twister (2019)
进阶 · 约 30 分钟读完前置知识：伪随机数生成器基础、统计随机性检验、状态空间与周期概念
导读
这篇论文主张是时候弃用 Mersenne Twister（MT19937）了：它状态体积大（约 2.5KB）、初始化/种子处理存在缺陷、速度不如现代生成器，并且未能通过部分严格的统计测试；作者建议改用状态更小、更快且经过严格测试的现代伪随机数生成器（如 xoshiro 系列）。
HN 关注点：选 PRNG 是很多工程师的日常决策，HN 讨论的焦点是：MT 之所以长期流行，是否只是因为它名字好记好听，以及 PCG、xorshift、xoshiro、WELL 等替代方案在体积、速度和跨平台一致性上的实际取舍。
HN 评论精选
这几条评论里：支持 1 质疑 1 亲历 2
支持认为 PCG/LCG 明显优于 MT，并给出对比资料。
PCG 和 LCG（置换线性同余生成器）似乎强得多。这是我最喜欢的相关演讲之一：https://www.youtube.com/watch?v=45Oet5qjlms ，这个矩阵对比也讲得很清楚：https://www.pcg-random.org/index.html
SethTro查看英文原文
PCG and LCG (permuted/linear congruential generator) seem much stronger. This is one of my favorite presentations on the subject https://www.youtube.com/watch?v=45Oet5qjlms&t=2s and this matrix breaks it down well https://www.pcg-random.org/index.html
亲历亲历教训：自研 PRNG 实现必须与参考实现逐位比对验证。
文中提到 WELL 家族很有意思。2011 年我在 TXR Lisp 里选了 WELL512，可惜实现一直有 bug，直到 2020 年 10 月才修好。:( 如果你要重新实现，别当牛仔：一定要验证你的结果与参考实现完全一致。
kazinator查看英文原文
Interesting mentions of the WELL family. I chose WELL512 for TXR Lisp back in 2011. Unfortunately, the implementation was bungled until October 2020. :( If you re-implement, don't be a cowboy: validate that you're getting identical results to the reference implementation.
亲历跨平台可复现性需求下 MT 太重，xorshift32 极小且够用。
作为一个普通人的数据点：我上周正好需要一个伪随机数生成器。场景是半嵌入式，两个跑在不同硬件和操作系统上的应用要生成完全相同的随机数据流。我一开始天真地用 rand()，但显然两个完全不同平台的 C 库不保证有相同的 PRNG，所以不行。像很多人一样，一想到“已知的” PRNG 实现，我第一个想到的就是 Mersenne Twister，于是去研究它。很快我就判断它对很多应用来说代码量和状态都太大了，于是继续找。最后选了 xorshift32，非常满意：核心实现约 10 行 C，整个模块（头文件+实现，带少量注释和一个伪 main 测试驱动）只有 60 行，状态只要 32 位，完全塞得下。
unwind查看英文原文
As just a datapoint from some random person, I needed a pseudo-random number generator just last week. My use-case is semi-embedded, with two applications running on different hardware and operating systems, that both needed to generate streams of the same random data. I first naively went with just rand() to get it running, but obviously there's no guerantee that two completely different platforms' C libraries have the same PRNGs. So that didn't work. Like many (?), the Mersenne Twister is the first name that pops into my head if I think of "known" PRNG implementations, so I investigated it. I quickly came to the conclusion that it was kind of large in terms of amount of code and state for many applications, so I kept looking. Eventually I went with xorshift32 [1] and am very happy with that choice. The core of the implementation is ~10 lines of C, and my entire module (header+implementation, with mild commenting and a faux-main() test "driver") is sitting at 60 lines. It needs a whopping 32 bits of state, which I could manage to squeeze in just fine. :) [1]: https://en.wikipedia.org/wiki/Xorshift
质疑质疑 xoshiro 也有缺陷，并追问模拟场景和 8 位单片机上的最佳选择。
这篇论文的作者推荐用 Xoshiro 家族里的 xoshiro256 作为替代。我看到这里有讨论说它也有致命缺陷，不过我不是专家（https://www.pcg-random.org/posts/a-quick-look-at-xoshiro256.html ）。我写路径追踪器的时候，随机数生成器的质量是肉眼可见的：我的编程语言自带的糟糕 LCG 让本应是随机噪声的地方出现了明显的图案。那么在不需要考虑可预测性的模拟场景里，现在最先进的选择是什么？另外我玩微控制器，只有 8 位 CPU、代码和内存都非常有限时，什么选择比较合适？
magicalhippo查看英文原文
The author of this paper suggests their xoshiro256 from the Xoshiro family[1] as an alternative. I found some discussion here[2] where it's suggested it has some fatal flaws as well, though I'm no expert. Back when I wrote a path tracer, the quality of the random number generator was visible. The poor LCG[3] that my programming language sported resulted in obvious patterns in what should have been random noise. So, for simulations where predictability etc is not a concern, what's the state of the art? And since I'm into microcontrollers, what's a decent choice when you only got a 8-bit CPU and very limited space (both code and memory)? [1]: http://xoroshiro.di.unimi.it/ [2]: https://www.pcg-random.org/posts/a-quick-look-at-xoshiro256.html [3]: https://en.wikipedia.org/wiki/Linear_congruential_generator
相关资源
从这篇论文所有 HN 讨论帖的全部评论里整理出来的链接。
历次讨论
- 2020Hacker News 讨论帖162 分 · 92 评
- 2022Hacker News 讨论帖99 分 · 52 评
同领域还值得读
哲学家为何应关注计算复杂性
Why Philosophers Should Care About Computational Complexity (2011)
Scott Aaronson 的这篇长文论证计算复杂性理论（如 P vs NP、停机问题的复杂度视角）对哲学问题（如知识的本质、中文房间、水槽论证等）具有实质意义，而不仅是技术细…
算法与理论计算机2015 · 552 分 · 120 评进阶 · 约 90 分钟编辑精选通信的数学理论
A Mathematical Theory of Communication
是香农1948年的《通信的数学理论》，为通信建立数学框架：把信息量定义为不确定性或自由度（信息熵），并讨论信源编码、信道容量与可靠传输。
算法与理论计算机2020 · 495 分 · 91 评进阶 · 约 120 分钟编辑精选物理、拓扑、逻辑与计算：罗塞塔石碑
Physics, Topology, Logic and Computation: A Rosetta Stone (2009)
用范畴论充当“罗塞塔石碑”，试图在量子物理、拓扑、逻辑与计算四个领域之间建立统一的结构性类比：物理中的量子过程、拓扑中的配边、逻辑中的证明和计算中的程序，都可被视为某类范畴中的态…
算法与理论计算机2009 · 390 分 · 55 评 · 引用 13专业 · 约 180 分钟编辑精选一种快速、极小内存的一致性哈希算法
A Fast, Minimal Memory, Consistent Hash Algorithm
论文给出一种快速、省内存的一致哈希方案，目标是在桶数量变化时保持较小的键迁移成本，同时降低计算和内存开销。
算法与理论计算机2014 · 327 分 · 57 评 · 引用 4进阶 · 约 25 分钟编辑精选第五个 Busy Beaver 值的确定
Determination of the fifth Busy Beaver value
宣布确定了第五个 Busy Beaver 值 BB(5)：即 5 状态图灵机中停机前运行步数最多的机器（Champion）在 47,176,870 步后停机。
算法与理论计算机2025 · 288 分 · 116 评 · 引用 1专业 · 约 75 分钟编辑精选