同一份账，六种加法，六个答案

let 收入 = 0, 支出 = 0;
for (const 分录 of 流水) 分录 >= 0 ? (收入 += 分录) : (支出 += 分录);
const 余额 = 收入 + 支出;

六种写法，一份数据

下面这六种，全部跑在同一份一百万条的流水上，同一台机器，同一个 double：

六个答案。最好和最差之间差了 七个数量级。

而且请注意排序：写起来最自然的那个是最差的。

① 为什么「先收后支再相减」最差

这个写法在业务上完全合理——报表本来就要分别列出收入和支出。可它在数值上是这一章所有陷阱的合体：

Σ收入 = 181 107 043 984 376.00 元
Σ支出 = −181 107 043 980 055.53 元
        └────────┬────────┘
         两个 1.8×10¹⁴ 的数

ulp(1.8×10¹⁴) = 0.03125 元      ← 相减之前，精度就只剩三分二厘了

相减 ⇒ 4320.46875

这是第 3 章那件事：两个几乎相等的大数相减。
κ = (1.8e14 + 1.8e14) / 4321.55 ≈ 8.4 × 10¹⁰

更值得看的是下面这个——就算两边的累加都用精确算术做（一次抹零都不发生），最后那一步减法还是要在 double 里做：

Σ收入（精确后存 double）= 181107043984375.06
Σ支出（精确后存 double）= −181107043980053.53
相减                    = 4321.53125
                          ⟨差 −0.01875 元⟩

★ 两边算得再准都没用。**问题出在「把它写成两个大数的差」这个决定上。**

这句话值得停一下。你在选择数据结构和计算顺序的时候，就已经把条件数定下来了。之后写多好的求和算法，都只是在一个已经被定死的天花板下面挣扎。

③ 排序为什么赢了，以及为什么它赢得可耻

「先加小的」是数值分析教科书里最常见的一条建议，第 4 章也提过。这里它确实拿了个不错的成绩（差 838 861 个 ulp，比朴素累加好三个数量级）。

但它赢的理由经不起看：每笔转账的 +v 和 −v 绝对值一模一样，按绝对值排序之后，它们被排到了紧挨着的位置，一加就当场对消。累加器因此从头到尾都待在很小的数上，脚下的刻度一直很细。

换一份数据——比如金额有零有整、正负不成对的真实流水——这个优势立刻消失。排序是一条依赖数据分布的建议，不是一条定理。而这一章要找的是不依赖运气的写法。

④ 成对求和：五行代码，免费的三个数量级

成对求和（pairwise summation）的想法一句话说完：别顺着加，对半分。

function pairwiseSum(a, lo = 0, hi = a.length) {
  const n = hi - lo;
  if (n <= 128) {                       // 小块直接加，让 CPU 跑满
    let s = 0;
    for (let i = lo; i < hi; i++) s += a[i];
    return s;
  }
  const mid = lo + (n >> 1);
  return pairwiseSum(a, lo, mid) + pairwiseSum(a, mid, hi);   // 分治
}

误差从 O(√n) 降到 O(√log n)——一百万个数，√n = 1000，√log₂n ≈ 4.5。而速度和朴素累加基本一样（因为小块内部还是顺序加，缓存友好；分治只多了 log n 层函数调用）。

这就是为什么 numpy.sum 默认就是它。不用你做任何事，你已经在用一个比 for 循环好三个数量级的求和算法了。

顺带一个很有意思的细节：这台机器上，我写的成对求和给出 4321.55029296875，而 numpy.sum 给出 4321.5501708984375——两个都叫「成对求和」，答案不一样，因为 numpy 的内层小块是按 8 路展开的，累加顺序不同。这一条会在第 19 章变成一整章。

⑤⑥ 补偿求和，以及 Kahan 为什么会输

补偿求和的想法更聪明：每加一次，都把「刚才被抹掉的那一点」算出来，存在一个小变量里，下一次加之前先补回去。

// Kahan（1965）
function kahanSum(a) {
  let s = 0, c = 0;                 // c 装着「上次欠下的」
  for (const x of a) {
    const y = x - c;                // 先把欠账还上
    const t = s + y;                // 加（这一步会抹零）
    c = (t - s) - y;                // ★ 算出这次抹掉了多少
    s = t;
  }
  return s;
}

第四行是全部的魔法：(t − s) 是「累加器实际增加了多少」，减去 y（本该增加多少），差就是被抹掉的量。而根据第 3 章的 Sterbenz 引理，这两步减法本身是精确的——补偿项被完整地捞了出来。

可是在这份数据上，Kahan 输给了 Neumaier，差了 4.31 × 10⁻⁶ 元。为什么？

因为 Kahan 有一个前提：|s| ≥ |x|，累加器比新来的数大。这时 (t − s) 才等于「s 增加的量」。而这份流水里金额跨了十二个数量级，经常有一笔 100 亿砸进一个只有几百块的累加器——这时候被抹掉的是 s 的低位，不是 x 的，Kahan 那行减法捞出来的东西就不对了。

Neumaier 在 1974 年补了这个洞，办法很朴素：比一下谁大，谁大就用谁的公式。

// Neumaier（1974）—— 也叫 Kahan–Babuška–Neumaier
function neumaierSum(a) {
  let s = 0, c = 0;
  for (const x of a) {
    const t = s + x;
    c += Math.abs(s) >= Math.abs(x)
       ? (s - t) + x                // 累加器大：丢的是 x 的低位
       : (x - t) + s;               // 新数大：★ 丢的是 s 的低位
    s = t;
  }
  return s + c;                     // 最后一次性补回
}

多了一个 if。就这一个 if，把 4.31×10⁻⁶ 的误差变成了 0——它在这份数据上给出的是正确舍入的结果，和精确算术逐位相同。

import math, random

random.seed(19910225)
led = [4321.55]                                  # 开盘余额
for _ in range(500_000):                         # 五十万笔转账 = 一百万条分录
    v = 10 ** random.uniform(-2, 10)             # 0.01 元 到 100 亿元
    led += [v, -v]                               # 复式记账：一出一进
random.shuffle(led)

def naive(a):
    s = 0.0
    for x in a: s += x
    return s

def kahan(a):
    s = c = 0.0
    for x in a:
        y = x - c; t = s + y; c = (t - s) - y; s = t
    return s

def neumaier(a):
    s = c = 0.0
    for x in a:
        t = s + x
        c += (s - t) + x if abs(s) >= abs(x) else (x - t) + s
        s = t
    return s + c

pos = [x for x in led if x >= 0]; neg = [x for x in led if x < 0]
print('① 先收后支再相减 ', repr(naive(pos) + naive(neg)))
print('② 朴素累加       ', repr(naive(led)))
print('③ 排序后累加     ', repr(naive(sorted(led, key=abs))))
print('⑤ Kahan          ', repr(kahan(led)))
print('⑥ Neumaier       ', repr(neumaier(led)))
print('★ math.fsum      ', repr(math.fsum(led)))
print('  真值应为        4321.55')

这一章的一句话

求和不是一个动作，是一个有六种写法、七个数量级差距的设计决策；而其中最贵的那笔账，是在你决定「先分组再相减」的那一刻就记下的。

卷 II 到这里结束。你现在有了完整的诊断工具：条件数（问题）、后向稳定（算法）、以及连接它们的那条公式。

卷 III 换一件事做：动手改。接下来四章里，每一章都是同一个动作——不换语言、不加精度、不改数据，只把式子换一种代数上完全等价的写法，然后看误差掉几个数量级。第一个例子是每个人初中就会的求根公式：解 x² + 10⁹x + 1 = 0，公式给出的小根是 0；改一行，得到 −10⁻⁹。