一个看似简单的计算器应用，背后隐藏着从浮点数精度到构造性实数再到数论猜想的层层深坑，Google 工程师 Boehm 的这段开发经历堪称编程史诗。

计算器应用？谁都能做——不，这可能是最难的编程挑战之一

一个看似简单的错误

如果你打开 iOS 自带的计算器，输入 (10^100) + 1 - (10^100)，你会得到 0。而正确答案是 1。Android 计算器却给出了正确的结果。

这个差异背后，是一段令人难以置信的工程故事——一个关于数值表示、数学深度和计算机科学极限的故事。

开篇：一个不可能的差事

Google 雇佣了 Hans-J. Boehm——没错，就是那位发明了 Boehm 垃圾回收器、主导了 C++ 共享变量语义定义的大神。他被视为精英中的精英，专门解决垃圾回收和并发编程中的疑难杂症。

然而，Google 却交给他一个看似简单、实则几乎不可能完成的任务：写一个计算器应用。

为什么浮点数不够用

计算器的核心目的是给用户正确的答案。但浮点数天生不精确——它们无法精确表示 0.3，也无法表示 10^100。用浮点数构建的计算器，就像建在沙地上的房子，随时可能崩塌。

这不是理论上的吹毛求疵。(10^100) + 1 在浮点数中会被舍入回 10^100，因为浮点数的尾数部分根本无法容纳这个数量级上的 +1 操作。这就是 iOS 计算器出错的原因。

IEEE 754 浮点数标准覆盖的只是有限的数字子集，而数学世界中的数字几乎无穷无尽。即便是看似简单的运算，只要涉及到浮点数，就需要极其谨慎的误差分析才能给出满意的答案。

第一层尝试：任意精度整数（Bignum）

解决某些问题的自然方案是使用 bignum——无边界整数。传统数值类型固定为 2 或 4 字节，而 bignum 按需分配内存，可以表示任意大的整数。

这解决了 (10^100) + 1 - (10^100) 的问题，因为每个中间结果都被精确表示。

但 bignum 只是整数。分数怎么办？

第二层尝试：任意精度有理数

分数的解法很直接：用 bignum 分别表示分子和分母。四则运算在这种类型上的实现并不复杂，而且永远给出精确答案。

到了这一步，很多人可能已经宣布胜利了。但 Boehm 并不满意，远远不满意。

第三层：代数数（Algebraic Numbers）

数学的深度远不止分数。π 或 √2 怎么办？

基于任意精度分数的计算器无法告诉你圆的周长——因为 π 无法表示为任何分数。如果计算器连九年级数学都无法正确处理，那它还有什么用？

Boehm 于是转向代数算术。这里不再将数字表示为分子分母，而是表示为它们所满足的多项式方程。例如，√2 可以表示为方程 x² - 2 = 0 的正根。

此时运算变得更加复杂：

• 加法：构造一个以两数之和为根的新多项式
• 乘法：使用多项式复合（polynomial composition）和结式（resultants）

这依然不够好。代数数方案只适用于代数数——而 π 是超越数，无法用任何多项式方程表示。

第四层：构造性实数（Constructive Reals）

Boehm 别无选择，只能继续深挖。从整数（bignum）到有理数，再到代数数，接下来是什么？构造性实数。

他开始研究"递归实数算术"（Recursive Real Arithmetic，RRA）。给定一个表达式和你想要的精度，RRA 返回一个至少达到该精度的结果。

经典的《Computability and Logic》教科书封面完美诠释了这一概念：尺子越变越小，逼近的精度越来越高。

构造性实数的核心思想：有些数字你永远无法完全写出所有小数位——例如 π。但如果我要求你给我一个离 π 在 0.01 之内有理数，你可以给我 3.14。这已经满足了题目要求。

RRA 的工作原理

假设我有一个函数可以生成 π 的数字序列（3.14159...）。现在我需要一个离 2π 在 0.01 以内的数。

我该如何利用 π 的近似值？关键洞察是：乘法会放大误差。乘以 2 会把误差翻倍。因此，要得到 2π 在 0.01 以内的近似值，我需要一个 π 在 0.005 以内的近似值。

于是取 π ≈ 3.141（确实离 π 小于 0.005），乘以 2 得到 6.282，这就是一个离 2π 在 0.01 以内的合法答案。

RRA 的正式定义：每个 RRA 数被表示为一个函数，该函数接收一个有理数（表示容忍误差），返回一个有理数（保证在指定容忍度内逼近真实值）。

这使 RRA 使用起来非常简单：你说出所需精度，系统递归地计算每个中间步骤需要多少精度。它轻松处理包含 π 或 √2 的表达式——这正是计算器所需要的。

困境：0.0000000000000 不是好答案

你可能会想："Boehm 到这里就该停了吧。设置输出精度为计算器显示位数不就行了？这样显示出来的所有数字都正确。"

但问题没那么简单。当用户输入 1-1 时，正确答案是 0，你希望显示 "0"。但 RRA 只会告诉你："1-1 在 0.0000000000000 的舍入误差范围内"。

在屏幕上显示一长串 0.0000000000000，而答案恰好是精确的 0，这是糟糕透顶的用户体验。没人想看到 0.0000000000000 作为计算结果。

相等性检测的不可判定性

Boehm 被迫回到设计绘图板。此时即使是他也不得不感到压力——他的"空间高效保守垃圾回收"跟这个问题相比简直是儿戏。他拉来了同事 Corky Cartwright 和 Vernon Lee Jr 一起攻坚。

问题核心在于：RRA 可以验证两个数不相等，但无法验证它们相等。

两个数不相等？你可以不断提高精度，直到在某个精度级别上看到它们的差值非零。但如果两个数确实相等，你将永远提高精度，永远等不到差异出现——这个过程永远不会终止。

举例：如果计算器对 e^(-10000) 显示 0，那是错误的——它并不等于 0。它应该显示 0.00000...，让用户滚动直到看到数字真正变化的地方。

但另一方面，当用户输入 sin(π) 时，应该显示 0，因为 sin(π) 恰好等于 0。RRA 却无法告诉我们 sin(π) 是精确的 0——它会一直计算，永远不会告诉你"这就是 0，停下来"。

（讽刺的是，iOS 计算器在这个问题上直接选择了不给出答案，哈哈。）

曙光：限制问题域

展示精确答案在构造性实数的框架下似乎是无解的。但 Boehm 和他的团队有了一个关键认识：他们不需要处理所有构造性实数。

他们只需要处理可以用计算器上可用操作表达的数。这些操作是：

1. 四则基本运算和平方根
2. 三角函数 sin、cos、tan 及其反函数
3. 指数函数和（自然）对数函数

这个集合比所有构造性实数小得多。

Richardson 与 Fitch 的 1994 年方案

事实上，已经有人研究过这个精确的问题。他们的名字是 Dan Richardson 和 John Fitch，他们在 1994 年解决了这个问题——早于 Boehm 参与这项工作的很多年前。

他们的解决方案在数学上是绝对正确的……除非某个数恰好构成了 Schanuel 猜想的反例。

Schanuel 猜想是数论中最重要的猜想之一，直到今天没有人找到反例。如果它是对的（几乎所有数学家都相信它是对的），那么 Richardson-Fitch 方案就是这样一幅精确而优雅的图景：

• 回答确定正确
• 在大多数情况下能终止并给出精确的答案（而不是逼近值）
• 在少数边缘情况下，可能需要依赖一个关于数论深层结构的未经证明的假设

尾声：是的，这个工程量级远超你的想象

所以，下次有人轻描淡写地说"计算器应用？谁都能做"时，你可以告诉他：这个问题的复杂度远超表面所见——从 IEEE 浮点数的精度陷阱，到任意精度整数、有理数、代数数的构建，再到构造性实数的理论研究，甚至触及了数论中最深层的未解难题。

为了给用户一个永远正确的答案，Boehm、Cartwright、Lee、Richardson 和 Fitch 这群顶尖计算机科学家和数学家，几乎触及了数值计算的哲学边界：什么是一个数字的"真实值"？我们如何保证每次回答都是正确的？在一个存在不可判定问题的数学体系内，我们究竟能做到多好？

也许"谁都能做"并不完全准确。但另一方面——至少，这种"不可能"的追求，正是计算机科学最美的部分。

---

原文链接: A calculator app? Anyone could make that

扩展阅读: The Impossible Calculator — Asterisk Magazine