HAKMEM
MIT 人工智能实验室备忘录 239
“我们编写这份报告，是希望记录下这里的人们所做的各种零散工作，以避免一些重复的努力——当然，为了好玩而重复的不算。”
M. Beeler
R.W. Gosper
R. Schroeppel
1972年2月29日
>> 星空篇：数论的奇境
从无穷素数到精巧的概率，HAKMEM 充满了对数字本质的深刻洞察和有趣猜想。
ITEM 29: 最大素数因子的概率
对于一个随机数 $X$，其最大素数因子落在特定区间的概率似乎是稳定的。以下是对 $10^{12}$ 附近数字的统计：
ITEM 52: 互质的概率
随机选取两个整数，它们互质（没有大于1的公因子）的概率是多少？答案出人意料地与 $\pi$ 相关。
≈ 60.79%
ITEM 56: 数字的“长度”
一个数的“长度”定义为反复将其各位数字相乘，直到得到一个个位数所需的迭代次数。例如，$277 \to 2 \times 7 \times 7 = 98 \to 9 \times 8 = 72 \to 7 \times 2 = 14 \to 1 \times 4 = 4$。长度为 5。
不同位数数字的最大长度
| 位数 (N) | 最大长度 |
|---|---|
| 2 | 4 |
| 3 | 5 |
| 4 | 6 |
| 5 | 7 |
| 8 | 9 |
| 10 | 10 |
猜想 (Schroeppel): 没有长度 > 10 的数。
12位数下不同长度的数字数量
ITEM 63: 239的魔力
数字 239 在 HAKMEM 中被反复提及，它联系了 $\pi$、无理数逼近和数论的多个方面，是黑客们钟爱的“明星数字”。
- $\pi$ 的 Machin 公式: $ \pi = 16 \arctan(\frac{1}{5}) - 4 \arctan(\frac{1}{239}) $ 与 $\sqrt{2}$ 的关系: $2 \times 13^4 - 1 = 239^2$, 这使得 $239/169$ 成为 $\sqrt{2}$ 的一个极佳逼近。 Waring 问题: 表达 239 需要 4 个平方数、9 个立方数、19 个四次方数 (均为最大需求量)。
- ...以及，这份备忘录的编号也是 239 (的后三位)。
>> 谜题篇：挑战与智慧
HAKMEM 不仅是答案集，更是一系列引人深思的谜题，从逻辑游戏到几何构造，至今仍有挑战性。
ITEM 80: 平方的平方 (Squared Square)
将一个正方形完美地分割成若干个大小不同的小正方形。图示为已知阶数最低的解（21阶，边长112），由 CSS Grid 实时生成。
ITEM 19: 双“非门”问题
一个经典的数字逻辑设计问题：
"用任意数量的与门（AND）和或门（OR），但只用两个非门（NOT），设计一个黑盒，输入 A、B、C，能输出 NOT-A、NOT-B 和 NOT-C。"
这个问题考验了对布尔函数可实现性的深刻理解。
PROBLEM: HAKMEM 中的开放问题
文档中许多“PROBLEM”标签标记的并非练习题，而是当时作者们也无法解决的难题。
- ITEM 2: 一个正n边形画上所有对角线，会分割出多少个区域？
- ITEM 39: 如何用3种数字构造出最长的字符串，使得其中没有任何连续重复的片段？
- ITEM 94-96: 在大棋盘上解决 Hex、西洋跳棋（Checkers）、国际象棋（Chess）和围棋（Go）。
>> 算法篇：代码中的魔法
HAKMEM 的核心是那些优雅、高效甚至有些诡异的算法和编程技巧，它们体现了“节省每一个周期”的黑客精神。
ITEM 149: Minsky 的圆周算法
一个无需三角函数或乘法（如果 $\varepsilon$ 是2的幂）就能绘制近似圆形的优雅算法。它实际上描绘了一个稳定的椭圆。
算法核心
以一个初始点 (OldX, OldY) 开始迭代：
这个微小的“错误”（使用 NewX 而非 OldX）赋予了算法惊人的稳定性。在定点数运算中，它会进入一个完美的循环。
ITEM 175: 统计一个字中的“1”比特数
一个经典的“位操作” (Bit Twiddling) 算法，在 PDP-6/10 汇编中只需10条指令，展示了并行计算思想的精髓。
ITEM 177: 增量曲线绘制 (Bresenham 算法的先驱)
如何在只能走“王字步”（水平、垂直、对角）的光栅显示器上精确绘制平滑曲线（如圆）？HAKMEM 描述了一种仅使用整数加减和比较的增量算法。
>> 遗产篇：HAKMEM 的回响
半个世纪过去了，HAKMEM 仍然是计算机科学领域的灵感源泉。它不仅是一份技术文档，更是一种文化象征，代表了那一代程序员对知识的纯粹热情和无限创造力。
“...猜猜这份备忘录是第几号？”
239
当然，它也是个素数。