floating-point - 为什么 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 。它只需要被加数(通常超过两个)。

我认为浮点运算手册邀请读者思考这种差异，但没有给出任何解释。无论如何，我已经考虑了一段时间，但我仍然不明白为什么 Kahan 的求和算法可以取消 ABS(a) > ABS(b) 测试(而且我现在手头没有这本书，因为我被提醒了这个问题)最近引用了 Kahan 的求和算法)。

Answer 1

简而言之，Kahan 求和的误差界限比 Add12 弱。 Kahan 求和获得相对于输入绝对值总和的误差有界。

查看 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 成正比。 Kahan summation 总是假设新输入更小，所以它得到的总误差大致与输入的绝对值之和成正比。

卡汉在描述卡汉总结的 original half-page paper 中写道:

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."