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

形式陈述

给定浮点序列 $x_1,\ldots,x_n$ ，目标是计算精确实数和

s=\sum_{i=1}^{n}x_i.

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

\left|\widehat s_n-s\right| \le \gamma_{n-1}\sum_{i=1}^{n}|x_i|, \qquad \gamma_{n-1}=\frac{(n-1)u}{1-(n-1)u}.

若 $s\ne0$ ，把绝对界除以 $|s|$ 会出现求和问题的条件因子

\frac{\sum_i|x_i|}{|\sum_i x_i|}.

同号数据的该因子为 $1$ ；正负项严重抵消时，它可以很大。这个比值属于“由给定各项求总和”的问题条件性， $\gamma_{n-1}$ 才描述顺序算法附加的舍入增长，两者不能压成一句“求和不稳定”。

成对求和把输入组织成近似平衡的二叉树，先求相邻小组，再逐层合并。它仍使用 $n-1$ 次加法，却把任一输入到根的舍入深度降到 $\lceil\log_2n\rceil$ ；对二的幂次长度，可得到形如

|\widehat s-s| \le\gamma_{\log_2n}\sum_i|x_i|

的界。非二次幂长度也可用不超过 $\lceil\log_2n\rceil$ 的不平衡末层处理。树形结构适合并行归约，但不同分块和调度会改变加法树，因而可能改变末位结果。

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

c=(t-s)-y

估计本轮被舍掉的低位，最后更新 $s=t$ 。校正量把一次加法未能写入主和的部分带到下一轮。在标准假设下，其经典误差界具有

|\widehat s-s| \le \bigl(2u+O(nu^2)\bigr)\sum_i|x_i|

的形态：相对于朴素求和，首阶项不再随 $n$ 线性增长；当 $nu^2$ 不小或中间溢出时，这个优势不能照搬。Neumaier 变体在新项比当前部分和更大时调整校正公式，对混合量级和某些强抵消排列更稳健；补偿运算本身仍会舍入，也不能改变病态求和的输入敏感性。

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

直觉

主累加器舍掉的低位进入补偿槽并在下一轮重新送回加法 — Kahan 补偿槽保留低位

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

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

例子与边界

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

1.000200000016548,

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

1.6548\times10^{-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”而允许编译器破坏其运算顺序，同样不能保留补偿语义。

推论与应用

误差推导以浮点算术标准误差模型 fl(a∘b)=(a∘b)(1+δ) 为共同起点；对相近大数相减或先形成巨大中间和的情形，则要借助消去误差与稳定重写判断是否应改变求和顺序、配对方式或补偿变量。

前缀和在精确结合运算下关注并行依赖结构，浮点输入还要同时说明每个前缀采用的加法树。点积、数值积分、统计均值、概率期望估计和快速 Fourier 变换都把大量局部结果归约为和，因此会继承本页的条件因子与顺序问题。

选择算法时可先看三个事实：项数是否足以让线性误差增长显著，正负抵消是否使精确和远小于绝对值之和，以及执行环境是否要求跨并行布局复现。同号、规模适中的串行数据常用朴素或成对求和已经足够；补偿适合准确性预算更紧而仍需 $O(n)$ 工作的场景；逐位可复现则需要固定归约树或专用累加器。没有这些信息，单独比较一次运行的最后几位无法判断方法是否可靠。

参考资料

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.

形式陈述 ​

反向链接

形式陈述