浮点求和：顺序、成对与补偿

形式陈述 ​

给定浮点序列公理库序列Sequence以自然数为定义域的函数。 $x_1,\dots ,x_n$，目标是计算精确实数和

$$s=\sum _{i=1}^n{x}_i.$$

朴素顺序求和按固定次序递推 ${\hat{s}}_k=\mathrm{fl}({\hat{s}}_{k-1}+x_k)$。在无溢出、采用标准舍入模型且 $(n-1)u<1$ 时，它满足典型前向误差界

$$|{\hat{s}}_n-s|\le {\gamma }_{n-1}\sum _{i=1}^n|x_i|,{\gamma }_{n-1}=\frac{(n-1)u}{1-(n-1)u}.$$

若 $s\ne 0$，相对误差界还会乘上求和问题的条件因子

$$\frac{\sum _i|x_i|}{|\sum _i{x}_i|}.$$

同号数据的该因子为 $1$；正负项严重抵消时，它可以很大。顺序求和的误差因此同时受项数、排列顺序和问题条件性影响。

成对求和把输入组织成近似平衡的二叉树，先求相邻小组，再逐层合并。它仍使用 $O(n)$ 次加法，却把一项参与舍入累积的树深降到 $O(\log n)$；对二的幂次长度，可得到形如

$$|\hat{s}-s|\le {\gamma }_{{\log }_{2}n}\sum _i|x_i|$$

的界。树形结构也适合并行归约，但不同分块和调度会改变加法树，因而可能改变末位结果。

Kahan 补偿求和额外维护一个校正量 $c$。每轮先令 $y=x_i-c$，再计算 $t=s+y$，并以

$$c=(t-s)-y$$

估计本轮被舍掉的低位，最后更新 $s=t$。校正量把一次加法未能写入主和的部分带到下一轮。Neumaier 变体在新项比当前部分和更大时调整校正公式，对混合量级和某些强抵消排列更稳健；补偿运算本身仍会舍入，也不能绕过溢出或病态求和。

“更准确”不是唯一目标。准确求和追求接近精确和或正确舍入结果；可复现求和要求线程数、分块或执行顺序改变时仍给同一位模式；高吞吐归约则关心带宽、向量化和同步成本。三者可以兼得一部分，却不是同一个规格，必须在算法说明中分别写清。

直觉 ​

顺序累加像不断往同一个刻度有限的量杯里加液体。当部分和已经很大，新加入的小量若小于当前一个刻度的一半，就会在舍入时完全消失。成对求和先让相近尺度的小量彼此合并，补偿求和则另放一个小杯子保存刚才没能倒进去的部分。

加法在实数中满足结合律，浮点加法却把每个括号位置变成一次舍入。重排不是改变数学目标，而是选择误差经过哪棵计算树传播；这也是串行代码、向量化实现和并行归约可能得到不同末位的原因。

例子与边界 ​

一次 binary64 实验从数值 $1$ 开始，依次累加 $\mathrm{2,000,000}$ 个 ${10}^{-10}$。高精度数学和为 $1.0002$；朴素循环得到

$$1.000200000016548,$$

相对于高精度参考舍入值的绝对误差约为

$$1.6548\times {10}^{-11}.$$

同一输入用 Kahan 求和得到打印值 $1.0002$，与该实验选用的正确舍入参考一致，所以记录的 binary64 误差为 $0$。这个结果只属于当前输入、顺序和精度；Kahan 并不保证任意序列都正确舍入，也不意味着数学实数 $1.0002$ 能被二进制浮点精确表示。

顺序依赖可由三项看清：

$$[{10}^{16},1,-{10}^{16}].$$

从左到右时，${10}^{16}+1$ 舍入回 ${10}^{16}$，最后得到 $0$；先把首尾相加则得到 $1$。精确和始终是 $1$，变化的是浮点括号结构。若数据本身正负相消严重，即使成对或补偿求和也只能减少算法附加误差，不能让病态问题变成良态。

编译器的重新结合、SIMD 分块和 GPU 归约可能合法地改变加法树。需要逐位可复现时，必须固定归约结构或使用专门的可复现算法；只声明“Kahan”而允许编译器破坏其运算顺序，同样不能保留补偿语义。

推论与应用 ​

前缀和公理库前缀和Prefix sum · Cumulative sum预先累计序列前缀，使静态区间和查询可由两个前缀值相减得到。在精确结合运算下关注并行依赖结构，浮点输入还要同时说明每个前缀采用的加法树。点积、数值积分、统计均值、概率期望公理库期望Expectation · Expected value实值或复值随机变量关于概率测度的 Lebesgue 积分。估计和快速 Fourier 变换都把大量局部结果归约为和，因此会继承本页的条件因子与顺序问题。

选择算法时可先看三个事实：项数是否足以让线性误差增长显著，正负抵消是否使精确和远小于绝对值之和，以及执行环境是否要求跨并行布局复现。没有这些信息，单独比较一次运行的最后几位无法判断方法是否可靠。

参考资料

• Nicholas J. Higham, Accuracy and Stability of Numerical Algorithms, 2nd ed., SIAM, 2002, Ch. 4.
• David Goldberg, “What Every Computer Scientist Should Know About Floating-Point Arithmetic,” ACM Computing Surveys 23(1), 1991.
• Takeshi Ogita, Siegfried M. Rump, and Shin’ichi Oishi, “Accurate Sum and Dot Product,” SIAM Journal on Scientific Computing 26(6), 2005.