← 揭开黑盒:理解系统的调查课堂

第二章 · 计算机选择的数学 / 第五单元 · 机器里的数

换一个顺序,还是同一道题吗?

上一节把一个“加不上去”的 1 找到了。现在有四个数:10^16、1、−10^16、1。它们的精确和是 2。你会怎样组织这四次输入?

预计用时:40 分钟。先在纸上按实数规则计算,再打开 加法顺序现场。

三条路,得到三个结果

左到右累加,从 0 出发。先加 10^16,再加 1;第二步的小量没有留下。接着减去 10^16,回到 0;最后加 1,结果是 1。

把相邻两项各自相加,再合并两个部分和,会形成另一棵计算树:(10^16 + 1) + (−10^16 + 1)。这组输入中两个小量都被舍入掉,得到 0。

补偿求和则为主累加器之外的小误差保留一个补偿量。本实验使用 Neumaier 形式,在这组输入上得到 2。

三者都在执行加法,也都可以写出在实数算术下等价的表达式。但在有限表示中,每个中间节点都可能发生舍入,计算树已经成为算法的一部分。

先打破一个过早的结论

如果你刚刚形成“配对更差”或“补偿永远精确”的判断,先保留它作为待检验解释。

在页面切换排列,把大数与负大数放在一起:10^16、−10^16、1、1。再把两个小数先放在一起。对每个排列先预测左到右的结果,然后观察。输入集合相同,实际顺序不同。

配对求和通常能减少长链中误差不断传递的机会,但不能保证对每一组数据都比某个顺序更准。补偿算法也使用有限精度,面对溢出、特殊值或很困难的输入时仍有边界。本节的精确对照成立,是因为这组小例子的整数和可以独立算清楚。

看补偿变量承担什么职责

在 algorithms.js/compensatedSum 中,total 保存主累加值,correction 累积局部加法没有充分保留的部分。它根据两个加数的量级,选择相应的表达式估计这部分差额,最后把补偿加入总和。

这意味着额外的判断、加减和状态。代码比简单的 total += value 更长,代价也更高;当输出精度有相应要求时,这些工作可能值得。

此时已有一种典型的“计算机选择的数学”:为了得到更可信的数值结果,我们调整计算过程,使它适应中间结果的表示限制。

并行也会改变这棵树

如果把一长串数据分给四个计算者,各自先求局部和,再合并结果,就改变了加法的组织。结果可能只差末位,也可能在困难输入上差得更多。后面讨论并行加速时,我们需要同时检查速度与误差。

因此,在比较两个实现前,要决定怎样判定“同一个答案”。某些任务要求完全可重复的位模式;某些任务使用绝对或相对误差界限;某些任务要求精确整数结果。这个选择应来自用途,不能等到结果不一致后才临时放宽。

本节交付:一棵计算树与一个反例

画出上述三种排列之一的左到右路径和配对路径,在会舍入的中间节点上做标记。再选一组新输入,预测结果并核对。可以先用 [1, 2, 3, 4] 检查并非所有输入都会产生差别,再设计包含相差很多量级的输入。

验收时应能解释一个结果为何出现,也能给出一个不支持“某方法永远更准”的边界。仅记住 1、0、2 三个数字还不够。

下一节继续问:除了排列同一串运算,我们能否 改写公式来避开困难的中间结果?