Was ist die numerisch genaueste Methode, um Summen oder Differenzen zu teilen?

Question

Betrachten (a-b)/(c-d) Betrieb, wo a, b, c und d sind Gleitkommazahlen (nämlich double Typ in C++). Sowohl (a-b) als auch (c-d) sind (sum - correction) Paare, wie in Kahan summation algorithm. Kurz gesagt, das Spezifische dieser (sum - correction) Paare ist, dass sum einen großen Wert relativ zu dem enthält, was in correction ist. Genauer gesagt, correction enthält, was nicht in sum während der Summation aufgrund numerischer Einschränkungen (53 Bits der Mantisse in double Typ) passen.

Was ist die numerisch genaueste Art zu berechnen (a-b)/(c-d) angesichts der oben genannten Spezialität der Zahlen?

Bonus Frage: es wäre besser, das Ergebnis auch als (sum - correction), wie in Kahan Summenalgorithmus zu bekommen. So zu finden (e-f)=(a-b)/(c-d), anstatt nur e=(a-b)/(c-d).

Answer 1

Der div2 Algorithmus von Dekker (1971) ist ein guter Ansatz.

Es erfordert einen mul12(p,q) Algorithmus, der genau ein Paar u+v = p*q berechnet. Dekker verwendet ein Verfahren, wie Veltkamp Aufspaltung bekannt, aber wenn Sie Zugriff auf eine fma Funktion haben, dann eine viel einfachere Methode ist

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

die eigentliche Teilung dann wie folgt aussieht (ich habe da einige der Zeichen ändern Dekker verwendet additive Paare anstelle von subtraktiven):

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

das die Summe r+s ist eine genaue Annäherung an (a-b)/(c-d).

UPDATE: Die Subtraktion und Addition angenommen linksassoziativ sein, dh

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

Dies funktioniert, weil, wenn wir lassen rr die Fehler bei der Berechnung von r (dh r + rr = a/c genau) sein, dann seit u+v = r*c genau, wir haben das rr*c = a-u-v genau, also also (a-u-v-b)/c ergibt eine recht gute Annäherung an den Korrekturterm von (a-b)/c.

Der letzte r*d ergibt sich aufgrund der folgenden:

(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 

Jetzt r ist auch eine ziemlich gute erste Annäherung an (a-b)/(c-d) so ersetzen wir in der [...], dass so finden wir, dass (a-u-v-b+r*d)/c eine gute Näherung an das ist Korrekturausdruck von (a-b)/(c-d)

Answer 2

Für kleine Korrekturen, denken vielleicht von

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