qinghuan
← 回到知识探索

计算机趣闻 / 可下载小项目

先加一个大数,再加1:那个1为什么消失了,又怎样把它找回来?

用一份补偿记录找回部分丢失的小量,再故意让补偿记录也舍入。比较朴素累加、Kahan、Neumaier 与精确输入参考。

展开本文目录
  1. 下载完整练习包
  2. 先动手看看
  3. 先约定“正确”是对哪一份输入求和
  4. 每次把小数塞回一个大和,小量可能一次次丢失
  5. Kahan:给下一次输入带上一张修正单
  6. Neumaier:比较两个加数大小,另存一份低位余额
  7. 实际运行:通过的是边界核验,不是“所有结果都精确”
  8. fsum 多记部分和,但参考仍要按具体契约理解
  9. 记录改进了多少,同时保留失败样例
  10. 记住这些要点
  11. 别把例子用过头
  12. 自己试一小步
  13. 查原始资料
开始前,会这些就够了
  • 会读循环、加减和列表;知道 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 检查环境和所在目录。文中标出的阅读时间只估算文章篇幅,安装环境和动手练习可按自己的节奏进行。

大数没有变,小数去哪里了?

正在准备实验控件…

输入:[1e+16, 1, -1e+16]

当前处理第几项
1/3
当前输入
1e+16
主和
1e+16
补偿项 correction
0
若此刻结束的结果
1e+16

Kahan 下次使用 x−correction;最终返回主和,不把 correction 按 Neumaier 的规则再加一次。

全部输入的精确和:1。先走完全部输入,再比较最终结果。

同时比较三种方法的最终结果
朴素逐项相加
0
Kahan 补偿
0
Neumaier 补偿
1

按 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 表示这些预期现象已复现,不能解释为三种算法在全部序列上都精确。

展开收起代码 · 小实验python · 108 行

长行可在代码区域内左右滚动,按 Tab 可把焦点移入代码区。

小实验 · python
"""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误解成所有求和结果与精确参考相同。

自己试一小步

能否让两种补偿算法出现不同结果,并解释差异来自哪一步?

  1. 自己选一个大数、几个小数和抵消项,先写出每个float的精确分数形式。
  2. 分别记录主和与修正;预测输出后再运行,比较重排前后的变化。
  3. 寻找一条Neumaier仍与一次舍入参考不同的序列,定位补偿项自身的舍入。
  4. 区分输入转换误差与累加误差,说明更换求和器能改善哪一种。

做到这些,就算完成

  • 精确参考不调用被测的补偿公式。
  • 既保存成功恢复的例子,也保存未恢复的例子。
  • 记录运行版本、输入范围和比较的是精确分数还是最终float。

查原始资料

想确认一个细节,先看这份资料对应的部分,不必从头读完所有文档。

  • Goldberg:Kahan Summation Formula (新标签页)↗David Goldberg / ACM 论文经许可重印于 Oracle Numerical Computation Guide · 英文

    Kahan 修正项的计算次序,以及浮点表达式不能随意按实数代数消去的原因。

    2026-10-23 实际打开并阅读:Theorem 8 的算法和相邻优化器说明,以及 Errors In Summation 的逐步修正解释;本文未复述其完整误差界证明;仅声明此范围,不代表通读整部资料。

  • CPython v3.14.0:CompensatedSum 与浮点 sum 分支 (新标签页)↗Python Software Foundation / CPython · 英文

    源码标注 Neumaier 改进算法,按两个加数的大小计算低位补偿;该版本内置 sum 的浮点快速路径调用它。

    2026-10-23 实际打开并阅读:CompensatedSum、cs_add、cs_to_double 及 builtin_sum_impl 的浮点快速路径;非有限值和混合类型路径不是本文教学函数的契约;仅声明此范围,不代表通读整部资料。

  • Python 3.14:math.fsum (新标签页)↗Python 官方文档 · 英文

    fsum 使用多份中间部分和,以及所依赖的浮点舍入条件和部分平台的末位限制。

    2026-10-23 实际打开并阅读:math.fsum 条目完整说明;用它作同域交叉对照,不把文档描述改成所有平台无限精确的承诺;仅声明此范围,不代表通读整部资料。

  • Python 3.14:Fraction.from_float (新标签页)↗Python 官方文档 · 英文

    将已经存储的浮点值精确转换成有理数;这与从原始十进制字符串构造并不相同。

    2026-10-23 实际打开并阅读:Fraction 构造器的浮点说明和 from_float 条目;仅声明此范围,不代表通读整部资料。