为什么Add12和Kahan的求和算法有区别？

Question

考虑下面的函数Add12，取自CRlibm\'s 文档，并修复了几个明显的拼写错误：

\n\n

\n

令a和b为浮点数，则以下方法计算两个浮点数s和r，使得s+ r= a+b恰好，并且是最接近+s的浮点数。ab

\n

\n\n

void Add12Cond ( double *s , double *r, double a, double b ) {\n  double z ;\n  *s=a+b;\n  if (ABS(a) > ABS(b)){\n    z=s\xe2\x88\x92a;\n    *r=b\xe2\x88\x92z; \n  } else {\n    z=s\xe2\x88\x92b;\n    *r=a\xe2\x88\x92z;\n  }\n}\n

\n\n

这看起来与应用于和的卡汉求和算法非常相似，但有一个明显的区别：卡汉的求和算法并不费心首先确定或中的哪一个最大。它只需要加数（通常是两个以上）。ababABS

\n\n

我认为浮点运算手册邀请读者思考这种差异，但没有给出任何解释。无论如何，我已经思考了一段时间，但我仍然没有任何直觉为什么卡汉的求和算法可以取消测试ABS(a) > ABS(b)（而且我手边没有这本书，所以我想起了这一点最近引用卡汉求和算法提出的问题）。

\n

Answer 1

简而言之，卡汉求和的误差界限比 更弱Add12。卡汉求和得到相对于输入绝对值之和的误差范围。

看看Add12，它确实计算s为最接近的东西a+b。条件是为了确保z精确计算（案例工作！），因此这r就是“其余的” a+b。特别是，你得到r + s = a + b和|r| <= 0.5 ulp(s)。

如果我们采用错误的分支，Add12但幅度差异不超过 2 epsilon，则z计算时最多会出现错误0.5 ulp(z)，因此*r计算时最多会出现错误1 ulp(z)。因此，无条件地选择两个分支中的一个意味着我们累积的误差与我们假设较小的事物的 ulp 成正比。卡汉求和总是假设新输入较小，因此它得到的总误差大致与输入绝对值之和成正比。

卡汉在他最初描述卡汉总结的半页论文中写道，这向我传达了《星际迷航》无法传达的关于 20 世纪 60 年代疯狂乐观情绪的信息：

许多 FORTRAN 和一些 ALGOL 编译器中双精度的方便访问表明双精度很快将被普遍接受，作为解决数值问题的独创性的替代品。

不幸的是，这篇半页纸没有给出界限或证据。TAOCP 第 4.2.2 节中的练习 19 给出了 Kahan 求和的误差界；该练习表明，x_1, ..., x_n 的 Kahan 求和所产生的误差以 (2 epsilon + O(n epsilon^2)) (sum(i=1..n) |x_i|) 为界。

我本来打算根据 TAOCP 中的设置给出一个证明，但一段时间以来我一直在重复地、令人尴尬地扼杀它。令人高兴的是，我刚刚发现大卫·戈德堡在《每个计算机科学家应该了解的浮点运算》的附录中这样做了。