开始前,会这些就够了
- 会读循环、加减和列表;知道
float只能保存有限精度。 - 先读 0.1加0.2为什么有小尾巴,区分存储的值和打印的文字。
遇到不熟悉的词,先看这 3 个解释
- 补偿求和
- 主和之外额外记录一些低位误差,减少连续累加造成的损失。
- 一次舍入参考
- 先对已存储输入精确求和,最后只把结果转换一次到
float。 - Neumaier修正
- 比较两个加数大小后计算低位修正,并另行累计补偿的求和方法。
依次累加 [1e16,1,1,-1e16],实数答案是2,但每次只把结果放回一个 float 的朴素循环会得到0。中间两个1太小,各自都没有改变已经很大的累计值。
多记一个补偿量可以改善这件事,但也有失败边界。下面先让 Kahan 找回2,再让它在另一组输入上失手,最后给 Neumaier 也找一个明确反例。
把例子带到自己的电脑上
下载完整练习包
需要 Python 3.10 或更新版本,无第三方依赖;实测 Windows / Python 3.14.0,Python 3.10 仅做语法兼容检查。使用标准库,不需要安装第三方包。下载 ZIP 后选择“全部提取”,进入能看到 README.md 的文件夹。
下载 ZIP · 5 个文件包里有什么
- demo.py:完整可运行源码
- README.md:运行步骤与练习
- observed.stdout.txt:本次实际输出
- verification.json:源码和运行验证记录
- SHA256SUMS.txt:文件摘要
在这个文件夹打开 PowerShell,逐行运行
python --version
python -B demo.py解压后,在含 demo.py 的目录打开终端。命令分别回车执行。binary64有限float教学域;19608条有限序列用Fraction精确输入和作参考,报告三法5810/4634/1644条舍入差异,明确Kahan及Neumaier反例;非通用库、非所有输入精确保证。
找不到命令或文件时,先按 README 检查环境和所在目录。文中标出的阅读时间只估算文章篇幅,安装环境和动手练习可按自己的节奏进行。
大数没有变,小数去哪里了?
正在准备实验控件…
按 JavaScript 的 binary64 运算展示三种求和过程,固定示例均为已经存入浮点数的整数,精确参考用这些存储值转换为 BigInt 后相加。两种补偿算法的 correction 定义不同;都不保证所有输入精确,输入转换前丢失的信息也无法恢复。
先约定“正确”是对哪一份输入求和
本例在二进制64位浮点环境运行,只接受最多10,000个有限 float,绝对值不超过1e100。这些范围让教学计算远离溢出;它不是处理 NaN、无穷和任意数字类型的通用库。
独立参考把每个已经存进 float 的值用 Fraction.from_float 精确变成分数,再用分数做加法。最后只转一次 float,得到本次比较用的舍入参考。这个过程没有沿用 Kahan 或 Neumaier 的补偿公式。
因此参考回答的是“这些已存储二进制数的和”。如果 10**16+1 在转 float 时已经变成1e16,后面的求和器看不到原来的那个1,也无法凭空还原;精确业务数据必须先在输入表示上保住。
每次把小数塞回一个大和,小量可能一次次丢失
本例朴素算法明确写 total=total+x。先存入1e16,再加1,附近可表示数的间隔已经大于1,这一步舍入后还是1e16。再加一个1又发生相同情况;最后减去1e16只剩0。
把输入换成 [1e16,-1e16,1,1],先抵消大数,再加两个1,就能得到2。数学实数加法可以随意结合,但逐步舍入的浮点运算不能据此假定顺序不影响答案。
不能把 Python 3.14 的内置 sum 当作这里的朴素循环。已读取的 CPython v3.14.0 源码中,浮点快速路径使用 Neumaier 补偿;为了让对照含义清楚,我们自己写顺序加法。
Kahan:给下一次输入带上一张修正单
Kahan 维护主和 total 与修正 correction。先算 adjusted=x-correction,再算 next_total=total+adjusted,接着用 (next_total-total)-adjusted 估计这一步没有进入主和的部分,保存给下一轮。括号和次序不能随意改写。
在 [1e16,1,1,-1e16] 中,第一个1没有进入主和,修正成为-1;下一个输入1减去-1,变成2,能够推动大和变化。最后与负的大数抵消,结果得到2。这里修正取负号是这份 Kahan 写法的约定。
它仍不是精确求和器。输入 [1e16,1,-1e16] 时,中间修正虽为-1,但下一轮计算 -1e16-(-1) 又把那个1舍掉,最终仍为0。保留一份修正记录,不代表所有后续运算都能无损使用它。
Neumaier:比较两个加数大小,另存一份低位余额
Neumaier 先计算 next_total=total+x,再比较 total 与 x 的绝对值。根据哪个更大,分别用 (total-next_total)+x 或 (x-next_total)+total 求这一轮的低位修正,将它累加到 correction,最后返回 total+correction。
对 [1e16,1,-1e16],中间的1被记为正的补偿余额。大数抵消后,主和为0、余额仍为1,最终返回1。注意这里的正余额与上一节 Kahan 的负修正不是同一个符号约定,不能把两套更新式拆开混用。
补偿余额自身也是 float,也可能丢精度。[1e100,1e16,1,-1e100,-1e16] 的精确输入和是1;这份 Neumaier 实现却得到0,因为记录中的1e16和1再次发生数量级悬殊的相加。改进了一个反例,并没有消除所有反例。
实际运行:通过的是边界核验,不是“所有结果都精确”
保存完整源码为 demo.py,执行 python demo.py。2026-10-23 在 Windows、CPython 3.14.0 实跑。默认四组结果分别展示小量恢复、Kahan反例、Neumaier反例和空输入;随后逐行打印两种补偿状态。
程序穷举长度0到5、元素取0、±1、±1e16、±1e-16的19,608条序列。与 Fraction 精确累加后仅一次转 float 的参考比较,朴素、Kahan、Neumaier 分别有5,810、4,634、1,644条结果不同。这是指定有限集合的实测,不是任意数据上的错误概率。
每条序列还与 math.fsum 交叉核对,本次集合全部一致。对 [1e16,1,-1e16] 的6种排列,朴素与Kahan各有2种得到1,Neumaier为6种;另检查输入转换丢失、空输入和8类拒绝输入。PASS 表示这些预期现象已复现,不能解释为三种算法在全部序列上都精确。
展开收起代码 · 小实验
长行可在代码区域内左右滚动,按 Tab 可把焦点移入代码区。
"""Compare rounded sums against the exact sum of the stored float inputs."""
from fractions import Fraction
from itertools import permutations, product
import math
import sys
def require(condition, message):
if not condition:
raise AssertionError(message)
def accumulate(values, mode, trace=False):
if not isinstance(values, (list, tuple)):
raise TypeError("list or tuple required for this teaching experiment")
if mode not in ("naive", "kahan", "neumaier"):
raise ValueError("unknown mode")
if len(values) > 10000 or any(type(x) is not float or not math.isfinite(x)
or abs(x) > 1e100 for x in values):
raise ValueError("at most 10000 finite floats with abs(x) <= 1e100")
total, correction, events = 0.0, 0.0, []
for i, x in enumerate(values):
if mode == "naive":
total = total + x
elif mode == "kahan":
adjusted = x - correction
next_total = total + adjusted
correction = (next_total - total) - adjusted
total = next_total
else:
next_total = total + x
if abs(total) >= abs(x):
correction += (total - next_total) + x
else:
correction += (x - next_total) + total
total = next_total
if trace:
events.append((i, x, total, correction))
result = total + correction if mode == "neumaier" else total
return result, events
def exact_sum(values):
result = Fraction(0)
for x in values:
result += Fraction.from_float(x)
return result
def main():
require(sys.float_info.radix == 2 and sys.float_info.mant_dig == 53, "binary64 required")
modes = ("naive", "kahan", "neumaier")
examples = [
("small_increments", [1e16, 1.0, 1.0, -1e16], (0.0, 2.0, 2.0), 2),
("kahan_counterexample", [1e16, 1.0, -1e16], (0.0, 0.0, 1.0), 1),
("neumaier_counterexample", [1e100, 1e16, 1.0, -1e100, -1e16], (-1e16, -1e16, 0.0), 1),
("empty", [], (0.0, 0.0, 0.0), 0),
]
for label, values, expected, rational in examples:
actual = tuple(accumulate(values, mode)[0] for mode in modes)
exact = exact_sum(values)
require(actual == expected and exact == rational, label)
require(math.fsum(values) == float(exact), "fsum comparison")
print(f"{label}: naive={actual[0]}; kahan={actual[1]}; neumaier={actual[2]}; exact={exact}")
for mode in ("kahan", "neumaier"):
_, events = accumulate([1e16, 1.0, -1e16], mode, trace=True)
for i, x, total, correction in events:
print(f"{mode}: i={i}; x={x}; total={total}; correction={correction}")
alphabet = (0.0, 1.0, -1.0, 1e16, -1e16, 1e-16, -1e-16)
mismatches = dict.fromkeys(modes, 0)
cases = 0
for n in range(6):
for values in product(alphabet, repeat=n):
rounded_reference = float(exact_sum(values))
require(math.fsum(values) == rounded_reference, "fsum differs on finite test domain")
for mode in modes:
actual = accumulate(values, mode)[0]
mismatches[mode] += actual != rounded_reference
cases += 1
require(all(mismatches[m] > 0 for m in modes), "each teaching algorithm has counterexamples")
permutation_matches = dict.fromkeys(modes, 0)
for values in permutations((1e16, 1.0, -1e16)):
for mode in modes:
permutation_matches[mode] += accumulate(values, mode)[0] == 1.0
require(permutation_matches == {"naive": 2, "kahan": 2, "neumaier": 6}, "order matters")
lost_at_input = [float(10**16 + 1), -1e16]
require(exact_sum(lost_at_input) == 0, "conversion already lost one")
require(all(accumulate(lost_at_input, m)[0] == 0.0 for m in modes), "cannot recover input")
invalid = [lambda: accumulate([1], "naive"), lambda: accumulate([True], "kahan"),
lambda: accumulate([math.inf], "neumaier"), lambda: accumulate([math.nan], "naive"),
lambda: accumulate([1e101], "kahan"), lambda: accumulate([0.0] * 10001, "naive"),
lambda: accumulate(iter([1.0]), "naive"), lambda: accumulate([], "unknown")]
rejected = 0
for action in invalid:
try:
action()
except (TypeError, ValueError):
rejected += 1
else:
raise AssertionError("invalid input accepted")
print(f"finite_sequences={cases}; rounded_reference_mismatches={mismatches}")
print(f"six_permutations_correct={permutation_matches}; input_conversion_exact_sum={exact_sum(lost_at_input)}")
print(f"rejected_inputs={rejected}; fsum_checked={cases + len(examples)}")
print("PASS: counterexamples reproduced; no universal exactness claim")
if __name__ == "__main__":
main()
怎样运行:在独立练习文件夹中,依次执行下载区的命令。2026-10-23 使用 Python 3.10 或更新版本,无第三方依赖;实测 Windows / Python 3.14.0,Python 3.10 仅做语法兼容检查 复跑这份源码并核对完整输出。binary64有限float教学域;19608条有限序列用Fraction精确输入和作参考,报告三法5810/4634/1644条舍入差异,明确Kahan及Neumaier反例;非通用库、非所有输入精确保证。
运行后对照结果
small_increments: naive=0.0; kahan=2.0; neumaier=2.0; exact=2
kahan_counterexample: naive=0.0; kahan=0.0; neumaier=1.0; exact=1
neumaier_counterexample: naive=-1e+16; kahan=-1e+16; neumaier=0.0; exact=1
empty: naive=0.0; kahan=0.0; neumaier=0.0; exact=0
kahan: i=0; x=1e+16; total=1e+16; correction=0.0
kahan: i=1; x=1.0; total=1e+16; correction=-1.0
kahan: i=2; x=-1e+16; total=0.0; correction=0.0
neumaier: i=0; x=1e+16; total=1e+16; correction=0.0
neumaier: i=1; x=1.0; total=1e+16; correction=1.0
neumaier: i=2; x=-1e+16; total=0.0; correction=1.0
finite_sequences=19608; rounded_reference_mismatches={'naive': 5810, 'kahan': 4634, 'neumaier': 1644}
six_permutations_correct={'naive': 2, 'kahan': 2, 'neumaier': 6}; input_conversion_exact_sum=0
rejected_inputs=8; fsum_checked=19612
PASS: counterexamples reproduced; no universal exactness claim
fsum 多记部分和,但参考仍要按具体契约理解
math.fsum 使用多份中间部分和,能够通过本例三层数量级反例。Python 文档同时说明它依赖浮点算术与舍入条件,部分平台可能出现一次额外舍入影响末位;本篇只报告当前运行环境与有限域的对照。
Fraction 参考采用有理数精确累加,计算和存储成本与整数位数有关,因此适合小实验审计,不能据此承诺海量流式统计也同样便宜。最终把精确分数转回 float 时仍可能需要舍入。
需要精确十进制业务结果时,应先选择保留业务值的输入与计算方式。把一个已经舍入的 float 交给 Fraction,只能精确保留那个浮点值;它不会自动把0.1猜回业务想要的十分之一。
记录改进了多少,同时保留失败样例
关闭 trace 时,三种教学算法每项做常数次固定精度浮点运算,总时间 O(n),只维护常数个浮点状态;打开轨迹会新增 O(n) 条记录。本函数为方便复验接收列表或元组,没有包装成持久化流处理接口。
测试比较的是数值结果,不是速度排名。不能因为Neumaier在这组枚举里差异更少,就声称它对每一条输入都优于Kahan;也不能因为某个例子返回整数,就省略对输入转换和中间舍入的检查。
评审累加代码时,可以依次问:输入原本想表示什么、当前float实际存了什么、每一步怎样舍入、参考怎么算、哪些反例仍失败。把这些信息写进实验记录,比只展示一个“修好了”的漂亮答案更可靠。
记住这些要点
- 朴素累加每一步都舍入,改变顺序可能改变结果。
- Kahan与Neumaier的补偿含义和符号约定不同,不能拼接公式。
- 补偿值也有有限精度,两种算法都有明确失败反例。
Fraction.from_float核对的是已存储输入,不能恢复输入转换前的信息。
别把例子用过头
- 把CPython 3.14内置sum标成朴素循环。
- 按实数代数约去补偿表达式,或弄反修正符号。
- 把有限枚举的差异条数当成普遍错误率或性能排名。
- 把返回PASS误解成所有求和结果与精确参考相同。
自己试一小步
能否让两种补偿算法出现不同结果,并解释差异来自哪一步?
- 自己选一个大数、几个小数和抵消项,先写出每个
float的精确分数形式。 - 分别记录主和与修正;预测输出后再运行,比较重排前后的变化。
- 寻找一条Neumaier仍与一次舍入参考不同的序列,定位补偿项自身的舍入。
- 区分输入转换误差与累加误差,说明更换求和器能改善哪一种。
做到这些,就算完成
- 精确参考不调用被测的补偿公式。
- 既保存成功恢复的例子,也保存未恢复的例子。
- 记录运行版本、输入范围和比较的是精确分数还是最终
float。
查原始资料
想确认一个细节,先看这份资料对应的部分,不必从头读完所有文档。
- Goldberg:Kahan Summation Formula (新标签页)↗
Kahan 修正项的计算次序,以及浮点表达式不能随意按实数代数消去的原因。
- CPython v3.14.0:CompensatedSum 与浮点 sum 分支 (新标签页)↗
源码标注 Neumaier 改进算法,按两个加数的大小计算低位补偿;该版本内置 sum 的浮点快速路径调用它。
- Python 3.14:math.fsum (新标签页)↗
fsum 使用多份中间部分和,以及所依赖的浮点舍入条件和部分平台的末位限制。
- Python 3.14:Fraction.from_float (新标签页)↗
将已经存储的浮点值精确转换成有理数;这与从原始十进制字符串构造并不相同。