OI 中浮点累加的误差补偿Kahan 求和算法原理、实现与实战【免费下载链接】OI-wiki:star2: Wiki of OI / ICPC for everyone. 某大型游戏线上攻略内含炫酷算术魔法项目地址: https://gitcode.com/GitHub_Trending/oi/OI-wikiKahan 求和补偿求和 / 进位求和是一类用于降低有限精度浮点数序列累加误差的数值算法通过一个单独变量持续累积每次舍入丢失的低位信息从而让长序列累加结果显著更接近真值。本文以 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成立$ab ba$结合律associativity不成立$(ab)c \neq a(bc)$。也就是说加法的顺序会影响结果。因此对于浮点序列求和既可以选择从左到右逐个累加朴素求和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(vectorfloat 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 vectordouble 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 中长浮点序列求和的首选Juliasum函数的默认实现是成对求和pairwise summation在精度与性能之间取得良好平衡对于需要更高精度的场景外部库sum_kbn提供了Neumaier 变体的实现即 Kahan 求和算法的改进版相关代码见 Julia 社区的 KahanSummation.jl 库。需要注意的是这些内置方案各有取舍fsum/sum_kbn侧重精度成对求和侧重性能在 OI 的 C 环境下没有标准库等价物因此手写 Kahan 求和仍是常用且轻量的做法。延伸阅读Kahan 求和本文对应的原始页面docs/basic/binary.md二分查找、三分法与二分答案浮点精度问题的常见发生场景docs/geometry/2d.md计算几何中的浮点精度问题讨论docs/lang/var.mdC 浮点类型与 IEEE-754 相关说明docs/misc/index.md本页所在的难以分类的算法板块索引。【免费下载链接】OI-wiki:star2: Wiki of OI / ICPC for everyone. 某大型游戏线上攻略内含炫酷算术魔法项目地址: https://gitcode.com/GitHub_Trending/oi/OI-wiki创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考