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

Question

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

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

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

Answer 1

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

它需要一个 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) 的校正项的良好近似值。