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

Question

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

Let a and b be floating-point numbers, then the following method computes two floating-point numbers s and r, such that s + r = a + b exactly, and s is the floating-point number which is closest to a + b.

void Add12Cond ( double *s , double *r, double a, double b ) {
  double z ;
  *s=a+b;
  if (ABS(a) > ABS(b)){
    z=s−a;
    *r=b−z; 
  } else {
    z=s−b;
    *r=a−z;
  }
}

这看起来与应用于 a 和 b 的 Kahan's summation algorithm 非常相似，但有一个明显的区别：Kahan 的求和算法不会首先确定 a 中的哪一个或者 b 有最大的 ABS。它只需要加数（通常超过两个）。

我认为Handbook of floating-point arithmetic 邀请reader考虑这个区别但没有给出任何解释。无论如何，我已经考虑了一段时间，但我仍然没有任何直觉可以理解为什么 Kahan 的求和算法可以取消 ABS(a) > ABS(b) 测试（而且我手头没有这本书，因为我被提醒了这个问题最近参考了 Kahan 的求和算法）。

Answer 1

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

查看 Add12，它肯定会计算出 s 最接近 a+b。条件是为了确保 z 得到准确计算（案例工作！），因此 r 是 "the rest of" a+b。特别是，您会得到 r + s = a + b 和 |r| <= 0.5 ulp(s)。

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

Kahan 在他的 original half-page paper 描述 Kahan 总结时写了以下内容，它向我传达了《星际迷航》无法传达的关于 1960 年代疯狂乐观的东西：

The convenient accessibility of double-precision in many FORTRAN and some ALGOL compilers indicates that double-precision will soon be universally acceptable as a substitute for ingenuity in the solution of numerical problems.

不幸的是，这篇半页纸没有给出界限或证明。 Kahan 求和的误差界在 TAOCP 第 4.2.2 节的练习 19 中给出；该练习指出，由 x_1、...、x_n 的 Kahan 求和引起的误差受 (2 epsilon + O(n epsilon^2)) (sum(i=1..n ) |x_i|).

我本来打算在这里根据 TAOCP 中的设置给出一个证明，但我已经反复和尴尬地屠宰了一段时间了。令人高兴的是，我刚刚发现 David Goldberg did this in the appendix to "What every computer scientist should know about floating-point arithmetic."

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

Why the difference between Add12 and Kahan's summation algorithm?

floating-point