除和或除差的最精确的数值方法是什么？

Question

考虑(a-b)/(c-d)操作，其中a、b、c和d是浮点数（即double输入 C++）。 (a-b) 和 (c-d) 都是 (sum-correction) 对，如 Kahan summation algorithm。简而言之，这些 (sum-correction) 对的具体情况是 sum 包含的值相对于 correction 中的值较大。更准确地说，correction 包含由于数值限制（double 类型中的 53 位尾数）在求和期间不适合 sum 的内容。

鉴于数字的上述特性，计算 (a-b)/(c-d) 的最精确的数值方法是什么？

奖金问题：最好将结果也作为 (sum-correction)，如 Kahan 求和算法。所以要找到 (e-f)=(a-b)/(c-d)，而不仅仅是 e=(a-b)/(c-d) .

Answer 1

对于微小的修正，可能会想到

(a - b) / (c - d) = a/b (1 - b/a) / (1 - c/d) ~ a/b (1 - b/a + c/d)

Answer 2

Dekker (1971)的div2算法是一个很好的方法。

它需要一个 mul12(p,q) 算法，它可以精确地计算一对 u+v = p*q。 Dekker 使用一种称为 Veltkamp 拆分的方法，但如果您可以访问 fma 函数，那么更简单的方法是

u = p*q
v = fma(p,q,-u)

实际除法看起来像（我不得不更改一些符号，因为 Dekker 使用加法对而不是减法）：

r   = a/c
u,v = mul12(r,c)
s   = (a - u - v - b + r*d)/c

总和 r+s 是 (a-b)/(c-d) 的准确近似值。

更新：假设减法和加法是左结合的，即

s = ((((a-u)-v)-b)+r*d)/c

这是有效的，因为如果我们让 rr 成为 r 的计算误差（即 r + rr = a/c 恰好），那么由于 u+v = r*c 恰好，我们有rr*c = a-u-v 完全正确，因此 (a-u-v-b)/c 对 (a-b)/c.

的校正项给出了相当好的近似值

最后的r*d是由于以下原因产生的：

(a-b)/(c-d) = (a-b)/c * c/(c-d) = (a-b)/c *(1 + d/(c-d)) 
            = [a-b + (a-b)/(c-d) * d]/c

现在 r 也是 (a-b)/(c-d) 的一个很好的初始近似值，所以我们在 [...] 中替换它，所以我们发现 (a-u-v-b+r*d)/c 是一个很好的近似值(a-b)/(c-d)

的修正项

除和或除差的最精确的数值方法是什么？

What is the most numerically precise method for dividing sums or differences?

algorithm

floating-point

sum

numeric

division