OI 中浮点累加的误差补偿：Kahan 求和算法原理、实现与实战-育师

OI 中浮点累加的误差补偿：Kahan 求和算法原理、实现与实战

【免费下载链接】OI-wiki:star2: Wiki of OI / ICPC for everyone. （某大型游戏线上攻略，内含炫酷算术魔法）项目地址: https://gitcode.com/GitHub_Trending/oi/OI-wiki

Kahan 求和（补偿求和 / 进位求和）是一类用于降低有限精度浮点数序列累加误差的数值算法，通过一个单独变量持续累积每次舍入丢失的低位信息，从而让长序列累加结果显著更接近真值。本文以 docs/misc/kahan-summation.md 为主体，结合 OI-wiki 仓库中的相关文档与代码，完整讲解其数学原理、逐行实现、在 OI 与竞赛程序中的辅助用法，以及 Python、Julia 等语言内置的高精度求和方案，帮助你在二分答案、计算几何等依赖浮点精度的场景中写出误差更小的代码。

引入：为什么要用 Kahan 求和

在浮点数累加长序列时，朴素从左到右的循环累加会不断累积舍入误差。Kahan 求和算法，又名补偿求和（compensated summation）或进位求和（carry summation）算法，通过保持一个单独变量（常用变量名 $c$）用来累积每次加法中被舍去的误差，从而把误差在后续迭代中"还回去"，得到更接近精确值的结果。

该算法主要由 William Kahan 于 1960s 提出；由于 Ivo Babuška 也曾独立提出过一个类似的算法，因此 Kahan 求和算法又被称为Kahan–Babuška 求和算法。在 OI 语境下，Kahan 求和通常不作为题目的核心考点，而是作为"辅助工具"存在——当题解需要累加浮点数、而朴素累加精度不足导致答案偏差时，用它替换普通累加即可。

在 OI-wiki 中，该页面位于"难以分类的算法及 OI 相关知识"板块（见 docs/misc/index.md），并在 mkdocs.yml 的导航中以 "Kahan 求和: misc/kahan-summation.md" 的形式收录，与模拟退火、随机化、CDQ 分治等杂项技巧并列，定位即是竞赛中拿来即用的"数值工具"。

舍入误差：浮点加法为什么不可靠

计算机使用有限位数对实数做近似表示，如今大多数机器遵循IEEE-754浮点数标准。例如 $\frac{1}{3}$ 无法在有限位数内精确表示，存储时必须截断（truncate）或四舍五入一部分数值，这种舍入误差（rounding off error）是浮点计算与生俱来的特征。

浮点加法的两个关键性质决定了朴素累加的误差来源：

交换律（commutativity）成立：$a+b = b+a$；
结合律（associativity）不成立：$(a+b)+c \neq a+(b+c)$。

也就是说，加法的顺序会影响结果。因此对于浮点序列求和，既可以选择从左到右逐个累加（朴素求和，naive summation），也可以保持原有顺序将元素两两配对求和（成对求和，pairwise summation）。后者速度相对较慢、需要更多内存，但因为中间和的数量更少、每次加法两操作数量级更接近，结果往往更准确，也被一些编程语言的求和函数默认采用（详见下文"编程语言的求和"一节）。

关于浮点近似表示与 IEEE-754 的更多背景，可参考仓库中 docs/lang/var.md 对浮点数类型的说明，以及其对 William Kahan 相关文献的引用。

误差的度量与补偿公式

为了定量描述每次加法丢失了多少精度，考虑一次累加

$$ S_{new} = S_{old} + a $$

其中 $a$ 是浮点序列中的一个数值。定义实际被加入 $S$ 的值为

$$ a_{eff} = S_{new} - S_{old} $$

注意这里的减法结果是在舍入后重新取出的值，因此 $a_{eff}$ 与真实参与加法的 $a$ 通常并不相等：

若 $a_{eff} > a$，说明存在向上舍入误差（结果被调大）；
若 $a_{eff} < a$，说明存在向下舍入误差（结果被调小）。

由此定义单次舍入误差

$$ E_{roundoff} = a_{eff} - a $$

那么用来纠正这部分误差的值就是 $a - a_{eff}$，即 $E_{roundoff}$ 的相反数。设 $c$ 为对丢失的低位进行运算补偿的变量，即可写出补偿变量的更新式：

$$ c_{new} = c_{old} + (a - a_{eff}) $$

这正是 Kahan 求和的核心思想：不丢弃误差，而是把它存进 $c$，在下一轮迭代加到被加数上。

过程与原理

Kahan 求和算法的主要过程就是维护两个变量：$sum$ 为最终返回的累加结果，$c$ 是对丢失的低位进行运算补偿的变量（即被舍去的部分），也是算法中必不可少的变量。

每次迭代的基本步骤如下：

用补偿量修正当前待加数：$y = a - c$；
累加：$t = sum + y$；
从结果中反推出这次加法实际丢失的低位：$c = (t - sum) - y$；
更新累加和：$sum = t$。

为什么这样有效？直观解释如下：由于 $sum$ 很大而 $y$ 很小，$sum + y$ 时 $y$ 的低位数会丢失。$(t - sum)$ 通过"大数减小数"抵消掉 $y$ 的高阶部分，再减去 $y$，就恢复了被舍去的那部分（$y$ 的低位部分）的相反数，存入 $c$。因此在代数意义上 $c$ 始终近似为零——它记录的不是累加和，而是当前累积的舍入误差。在下一轮迭代中，$c$ 中的丢失低位会被合并进 $y$，从而逐步把此前所有被舍掉的精度"补回"累加和。

从数值上看，Kahan 求和相对朴素求和的误差从 $O(n\varepsilon)$ 量级（$n$ 为项数、$\varepsilon$ 为机器精度）显著下降，代价仅是每次迭代多出若干次浮点加减法，在 $O(n)$ 的算法整体复杂度上没有额外代价，非常适合竞赛环境。

参考实现

原文档给出的 C++ 参考实现如下：

float kahanSum(vector<float> nums) { float sum = 0.0f; float c = 0.0f; for (auto num : nums) { float y = num - c; float t = sum + y; c = (t - sum) - y; sum = t; } return sum; }

若在 OI 中需要对double类型的长序列求和，把类型替换为double即可，逻辑完全一致：

double kahanSum(const vector<double>& nums) { double sum = 0.0; double c = 0.0; // 补偿变量，累积每次加法丢失的低位 for (double num : nums) { double y = num - c; double t = sum + y; c = (t - sum) - y; sum = t; } return sum; }

注意事项：

$c$ 本身也是浮点数，极端情况下（累加项数极多、量级差异极大）补偿量自身也会发生舍入，Kahan 求和并不能做到精确求和，只是把误差大幅压低；
在要求更高精度时可换用Neumaier 变体（对 $(t - sum) - y$ 按实际符号累加进补偿变量），它比标准 Kahan 求和更稳健，也是 Julia 生态中sum_kbn的默认实现（见下文）；
对于精确求和需求，应直接使用语言内置的精确/高精度求和函数，而不是手写补偿求和。

在 OI 中的典型应用场景

在 OI 中，Kahan 求和主要作为辅助工具存在，为计算结果提供误差更小的值，本身很少作为独立考点。常见的结合场景包括：

浮点二分答案 / 实数三分：当二分/三分精度收敛需要大量迭代、每次迭代都对大量浮点数累加判断可行性时，朴素累加的误差可能让check函数在临界值附近"抖动"，导致二分结果偏差。此时用 Kahan 求和替换普通累加更稳。仓库中 docs/basic/binary.md 讲解的二分答案与三分法正是这类场景，其配套代码 docs/basic/code/binary/binary_1.cpp 中即以constexpr double eps = 1e-7;控制实数收敛精度，累加误差越小，越不容易在eps量级上出错；
计算几何：仓库 docs/geometry/2d.md 指出计算几何经常进行double浮点运算、因此带来精度问题，多边形面积、重心等需要大量累加的几何量计算可受益于补偿求和；
概率 / 期望类题目：对大量浮点概率值累加（如期望的线性叠加）时同样存在长序列累加误差问题。

例题

以下两道 Codeforces 例题在原文档中被用于展示 Kahan 求和的实际应用场景（此处仅转述题面，不再附外链，可在 Codeforces 题库中按题目编号检索）。

例题一：Voltage Keepsake

有 $n$ 个同时使用的设备。第 $i$ 个设备每秒使用 $a_{i}$ 单位的功率，这种用法是连续的——在 $\lambda$ 秒内设备将使用 $\lambda \times a_{i}$ 单位的功率。第 $i$ 个设备当前存储了 $b_{i}$ 单位的电力，所有设备都可以存储任意数量的电量。有一个充电器，可以插入任何单个设备，每秒为设备增加 $p$ 单位的电量（充电同样是连续的）。我们可以在任意时间单位内（包括实数）切换哪个设备正在充电，切换时间忽略不计。求在其中一个设备达到 $0$ 单位功率之前，可以使用这些设备的最长时间。

该题的标准解法是对"最长时间 $t$"做浮点二分，而每个设备的耗电/充电比较需要对 $n$ 个浮点数进行累加比较，属于典型的"二分答案 + 浮点累加"场景，使用 Kahan 求和可以让二分中的可行性判断更稳定。

例题二：Misha and Permutations Summation

定义数字 $0, 1, \cdots, (n-1)$ 的两个排列 $p$ 和 $q$ 的和为 $Perm((Ord(p)+Ord(q)) \bmod n!)$，其中 $Perm(x)$ 是数字 $0,1,\cdots,(n-1)$ 的第 $x$ 个字典排列（从零开始计数），$Ord(p)$ 是字典序排列 $p$ 的个数。例如 $Perm(0) = (0,1,\cdots,n-2,n-1)$，$Perm(n!-1)=(n-1,n-2,\cdots,1,0)$。Misha 有两个排列 $p$ 和 $q$，求它们的总和。

该题与排列序号的康托展开思想相关，涉及大量基于浮点/大数中间结果的累加运算，同样需要在意累加的数值稳定性。

编程语言的求和方案

除了手写 Kahan 求和，主流语言也提供了高精度求和的内置方案，竞赛与工程中可根据语言直接选用：

Python：标准库math.fsum指定了精确舍入求和（correctly-rounded summation），可返回可迭代对象中所有值的准确浮点总和。它通过Shewchuk 算法跟踪多个中间部分和（partial sums）来避免精度损失，复杂度为 $O(n)$，是 Python 中长浮点序列求和的首选；
Julia：sum函数的默认实现是成对求和（pairwise summation），在精度与性能之间取得良好平衡；对于需要更高精度的场景，外部库sum_kbn提供了Neumaier 变体的实现（即 Kahan 求和算法的改进版），相关代码见 Julia 社区的 KahanSummation.jl 库。

需要注意的是，这些内置方案各有取舍：fsum/sum_kbn侧重精度，成对求和侧重性能；在 OI 的 C++ 环境下没有标准库等价物，因此手写 Kahan 求和仍是常用且轻量的做法。