Ist es möglich, 0 durch Subtrahieren von zwei ungleichen Gleitkommazahlen zu erhalten?

131

Ist es im folgenden Beispiel möglich, eine Division durch 0 (oder unendlich) zu erhalten?

public double calculation(double a, double b)
{
     if (a == b)
     {
         return 0;
     }
     else
     {
         return 2 / (a - b);
     }
}

Im Normalfall wird dies natürlich nicht der Fall sein. Was aber, wenn aund bsehr nahe beieinander liegen, kann (a-b)dies 0auf die Genauigkeit der Berechnung zurückzuführen sein?

Beachten Sie, dass diese Frage für Java gilt, aber ich denke, dass sie für die meisten Programmiersprachen gilt.

Thirler
quelle
49
Ich müsste alle Kombinationen von Doppel versuchen, das wird eine Weile dauern :)
Thirler
3
@ Thirler klingt für mich nach einer Zeit, um JUnit Testing zu verwenden!
Matt Clark
7
@bluebrain, meine Vermutung ist, dass Ihre Literalzahl 2.000 usw. zu viele Dezimalstellen enthält, um durch einen Float dargestellt zu werden. Die letzten werden also nicht durch die tatsächlich verwendete Zahl im Vergleich dargestellt.
Thirler
4
@ Thirler wahrscheinlich. "Sie können nicht wirklich garantieren, dass die Nummer, die Sie dem Float oder Double zuweisen, genau ist"
guness
4
Beachten Sie nur, dass die Rückgabe von 0 in diesem Fall zu schwer zu debuggenden Mehrdeutigkeiten führen kann. Stellen Sie daher sicher, dass Sie wirklich 0 zurückgeben möchten, anstatt eine Ausnahme auszulösen oder eine NaN zurückzugeben.
m0skit0

Antworten:

132

Ist in Java a - bniemals gleich 0if a != b. Dies liegt daran, dass Java IEEE 754-Gleitkommaoperationen vorschreibt, die denormalisierte Zahlen unterstützen. Aus der Spezifikation :

Insbesondere erfordert die Java-Programmiersprache die Unterstützung von denormalisierten Gleitkommazahlen nach IEEE 754 und einen allmählichen Unterlauf, wodurch es einfacher wird, wünschenswerte Eigenschaften bestimmter numerischer Algorithmen nachzuweisen. Gleitkommaoperationen "spülen nicht auf Null", wenn das berechnete Ergebnis eine denormalisierte Zahl ist.

Wenn eine FPU mit denormalisierten Zahlen arbeitet , kann das Subtrahieren ungleicher Zahlen niemals Null ergeben (im Gegensatz zur Multiplikation). Siehe auch diese Frage .

Für andere Sprachen kommt es darauf an. In C oder C ++ ist beispielsweise die IEEE 754-Unterstützung optional.

Dies gesagt wird , ist es möglich , die für die Expression 2 / (a - b)zu Überlauf, zum Beispiel mit a = 5e-308und b = 4e-308.

nwellnhof
quelle
4
OP möchte jedoch etwas über 2 / (ab) wissen. Kann dies garantiert endlich sein?
Taemyr
Vielen Dank für die Antwort. Ich habe einen Link zu Wikipedia hinzugefügt, um denormalisierte Zahlen zu erklären.
Thirler
3
@ Taemyr Siehe meine Bearbeitung. Die Aufteilung kann tatsächlich überlaufen.
Nwellnhof
@ Taemyr (a,b) = (3,1)=> 2/(a-b) = 2/(3-1) = 2/2 = 1Ob dies mit IEEE-Gleitkomma zutrifft, weiß ich nicht
Cole Johnson
1
@DrewDormann IEEE 754 ist auch für C99 optional. Siehe Anhang F der Norm.
Nwellnhof
50

Was ist als Problemumgehung mit den folgenden?

public double calculation(double a, double b) {
     double c = a - b;
     if (c == 0)
     {
         return 0;
     }
     else
     {
         return 2 / c;
     }
}

Auf diese Weise sind Sie in keiner Sprache auf IEEE-Unterstützung angewiesen.

Malarres
quelle
6
Vermeiden Sie das Problem und vereinfachen Sie den Test auf einmal. Ich mag.
Joshua
11
-1 Wenn a=b, sollten Sie nicht zurückkehren 0. Wenn Sie 0in IEEE 754 durch dividieren, erhalten Sie unendlich, keine Ausnahme. Sie vermeiden das Problem, daher ist die Rückkehr 0ein Fehler, der darauf wartet, passiert zu werden. Überlegen Sie 1/x + 1. Wenn x=0, das in Folge würde 1, nicht der richtige Wert: unendlich.
Cole Johnson
5
@ColeJohnson Die richtige Antwort ist auch nicht unendlich (es sei denn, Sie geben an, von welcher Seite das Limit stammt, rechte Seite = + inf, linke Seite = -inf, nicht angegeben = undefiniert oder NaN).
Nick T
12
@ ChrisHayes: Dies ist eine gültige Antwort auf die Frage, die erkennt, dass die Frage ein XY-Problem sein kann: meta.stackexchange.com/questions/66377/what-is-the-xy-problem
slebetman
17
@ColeJohnson Rückkehr 0ist nicht wirklich das Problem. Dies ist, was das OP in der Frage tut. Sie können eine Ausnahme setzen oder was auch immer für die Situation in diesem Teil des Blocks angemessen ist. Wenn Sie nicht gerne zurückkehren 0, sollte dies eine Kritik an der Frage sein. Wenn Sie das tun, was das OP getan hat, ist dies sicherlich keine Ablehnung der Antwort. Diese Frage hat nichts mit weiteren Berechnungen nach Abschluss der angegebenen Funktion zu tun. Nach allem, was Sie wissen, müssen die Anforderungen des Programms zurückgegeben werden 0.
jpmc26
25

Sie würden unabhängig vom Wert von keine Division durch Null erhalten a - b, da die Gleitkommadivision durch 0 keine Ausnahme auslöst. Es gibt die Unendlichkeit zurück.

Der einzige Weg a == b, um true zurückzugeben, ist if aund benthält genau die gleichen Bits. Wenn sie sich nur um das niedrigstwertige Bit unterscheiden, ist der Unterschied zwischen ihnen nicht 0.

EDIT:

Wie Bathseba richtig kommentierte, gibt es einige Ausnahmen:

  1. "Keine Zahl vergleicht" false mit sich selbst, weist jedoch identische Bitmuster auf.

  2. -0.0 ist definiert, um true mit +0.0 zu vergleichen, und ihre Bitmuster sind unterschiedlich.

Wenn also beide aund bsind Double.NaN, erreichen Sie die else-Klausel, aber da NaN - NaNauch zurückgegeben wird NaN, werden Sie nicht durch Null dividieren.

Eran
quelle
11
Eran; nicht unbedingt wahr. "Keine Zahl vergleicht" false mit sich selbst, weist jedoch identische Bitmuster auf. Außerdem wird -0.0 definiert, um true mit +0.0 zu vergleichen, und ihre Bitmuster sind unterschiedlich.
Bathsheba
1
@Bathsheba Ich habe diese Sonderfälle nicht berücksichtigt. Danke für den Kommentar.
Eran
2
@Eran, sehr guter Punkt, dass die Division durch 0 unendlich in einem Gleitkomma zurückgibt. Fügte es der Frage hinzu.
Thirler
2
@Prashant, aber die Division würde in diesem Fall nicht stattfinden, da a == b true zurückgeben würde.
Eran
3
Eigentlich könnte man eine FP-Ausnahme für die Division durch Null bekommen, es ist eine Option, die durch den IEEE-754-Standard definiert ist, obwohl es wahrscheinlich nicht das ist, was die meisten Leute mit "Ausnahme" meinen würden;)
Voo
17

Es gibt keinen Fall, in dem hier eine Division durch Null stattfinden kann.

Der SMT Solver Z3 unterstützt präzise IEEE-Gleitkomma-Arithmetik. Lassen Sie uns Z3 bitten, Zahlen zu finden aund bso, dass a != b && (a - b) == 0:

(set-info :status unknown)
(set-logic QF_FP)
(declare-fun b () (FloatingPoint 8 24))
(declare-fun a () (FloatingPoint 8 24))
(declare-fun rm () RoundingMode)
(assert
(and (not (fp.eq a b)) (fp.eq (fp.sub rm a b) +zero) true))
(check-sat)

Das Ergebnis ist UNSAT. Es gibt keine solchen Nummern.

Mit der obigen SMTLIB-Zeichenfolge kann Z3 auch einen beliebigen Rundungsmodus auswählen ( rm). Dies bedeutet, dass das Ergebnis für alle möglichen Rundungsmodi gilt (von denen es fünf gibt). Das Ergebnis beinhaltet auch die Möglichkeit, dass eine der im Spiel befindlichen Variablen NaNunendlich ist.

a == bwird als fp.eqQualität so implementiert +0fund -0fgleich vergleichen. Der Vergleich mit Null wird ebenfalls mit implementiert fp.eq. Da die Frage darauf abzielt, eine Division durch Null zu vermeiden, ist dies der geeignete Vergleich.

Wenn der Gleichheitstest wurde mit bitweise Gleichheit, umgesetzt +0fund -0fein Weg gewesen wäre , um a - bNull. Eine falsche Vorgängerversion dieser Antwort enthält Modendetails zu diesem Fall für Neugierige.

Z3 Online unterstützt die FPA-Theorie noch nicht. Dieses Ergebnis wurde unter Verwendung des neuesten instabilen Zweigs erhalten. Es kann mit den .NET-Bindungen wie folgt reproduziert werden:

var fpSort = context.MkFPSort32();
var aExpr = (FPExpr)context.MkConst("a", fpSort);
var bExpr = (FPExpr)context.MkConst("b", fpSort);
var rmExpr = (FPRMExpr)context.MkConst("rm", context.MkFPRoundingModeSort());
var fpZero = context.MkFP(0f, fpSort);
var subExpr = context.MkFPSub(rmExpr, aExpr, bExpr);
var constraintExpr = context.MkAnd(
        context.MkNot(context.MkFPEq(aExpr, bExpr)),
        context.MkFPEq(subExpr, fpZero),
        context.MkTrue()
    );

var smtlibString = context.BenchmarkToSMTString(null, "QF_FP", null, null, new BoolExpr[0], constraintExpr);

var solver = context.MkSimpleSolver();
solver.Assert(constraintExpr);

var status = solver.Check();
Console.WriteLine(status);

Mit Z3 IEEE Float Fragen zu beantworten ist schön , weil es schwer ist , Fälle zu übersehen (wie NaN, -0f, +-inf) und Sie können beliebige Fragen stellen. Keine Notwendigkeit, Spezifikationen zu interpretieren und zu zitieren. Sie können sogar gemischte Float- und Integer-Fragen stellen, z. B. "Ist dieser bestimmte int log2(float)Algorithmus korrekt?".

usr
quelle
Können Sie bitte einen Link zu SMT Solver Z3 und einen Link zu einem Online-Dolmetscher hinzufügen? Während diese Antwort völlig legitim erscheint, kann jemand denken, dass diese Ergebnisse falsch sind.
AL
12

Die bereitgestellte Funktion kann tatsächlich unendlich zurückgeben:

public class Test {
    public static double calculation(double a, double b)
    {
         if (a == b)
         {
             return 0;
         }
         else
         {
             return 2 / (a - b);
         }
    }    

    /**
     * @param args
     */
    public static void main(String[] args) {
        double d1 = Double.MIN_VALUE;
        double d2 = 2.0 * Double.MIN_VALUE;
        System.out.println("Result: " + calculation(d1, d2)); 
    }
}

Die Ausgabe ist Result: -Infinity.

Wenn das Ergebnis der Division zu groß ist, um in einem Doppel gespeichert zu werden, wird unendlich zurückgegeben, selbst wenn der Nenner nicht Null ist.

D Krüger
quelle
6

In einer Gleitkommaimplementierung, die IEEE-754 entspricht, kann jeder Gleitkommatyp Zahlen in zwei Formaten enthalten. Eins ("normalisiert") wird für die meisten Gleitkommawerte verwendet, aber die zweitkleinste Zahl, die es darstellen kann, ist nur ein kleines bisschen größer als die kleinste, und daher ist der Unterschied zwischen ihnen nicht in demselben Format darstellbar. Das andere ("denormalisierte") Format wird nur für sehr kleine Zahlen verwendet, die im ersten Format nicht darstellbar sind.

Schaltungen zur effizienten Handhabung des denormalisierten Gleitkommaformats sind teuer, und nicht alle Prozessoren enthalten sie. Einige Prozessoren bieten die Wahl, ob Operationen mit wirklich kleinen Zahlen viel langsamer sind als Operationen mit anderen Werten, oder ob der Prozessor Zahlen, die für ein normalisiertes Format zu klein sind, einfach als Null betrachtet.

Die Java-Spezifikationen implizieren, dass Implementierungen das denormalisierte Format unterstützen sollten, selbst auf Computern, auf denen Code langsamer ausgeführt wird. Auf der anderen Seite ist es möglich, dass einige Implementierungen Optionen bieten, mit denen Code schneller ausgeführt werden kann, wenn die Werte leicht schlampig behandelt werden, was für die meisten Zwecke viel zu klein wäre, um eine Rolle zu spielen (in Fällen, in denen Werte zu klein sind, um eine Rolle zu spielen) Es kann ärgerlich sein, wenn Berechnungen mit ihnen zehnmal so lange dauern wie wichtige Berechnungen. In vielen praktischen Situationen ist es daher nützlicher, auf Null zu gehen (langsame, aber genaue Arithmetik).

Superkatze
quelle
6

In früheren Zeiten vor IEEE 754 war es durchaus möglich, dass a! = B nicht ab! = 0 implizierte und umgekehrt. Dies war einer der Gründe, IEEE 754 überhaupt erst zu schaffen.

Mit IEEE 754 ist dies fast garantiert. C- oder C ++ - Compiler dürfen eine Operation mit höherer Genauigkeit als erforderlich ausführen. Wenn also a und b keine Variablen, sondern Ausdrücke sind, bedeutet (a + b)! = C nicht (a + b) - c! = 0, da a + b einmal mit höherer Genauigkeit und einmal ohne berechnet werden könnte höhere Präzision.

Viele FPUs können in einen Modus umgeschaltet werden, in dem sie keine denormalisierten Zahlen zurückgeben, sondern durch 0 ersetzen. In diesem Modus sind a und b winzige normalisierte Zahlen, bei denen die Differenz kleiner als die kleinste normalisierte Zahl, aber größer als 0 ist, a ! = b garantiert auch nicht a == b.

"Niemals Gleitkommazahlen vergleichen" ist Frachtkultprogrammierung. Unter den Menschen, die das Mantra "Sie brauchen ein Epsilon" haben, haben die meisten keine Ahnung, wie sie dieses Epsilon richtig auswählen sollen.

gnasher729
quelle
2

Ich kann mir einen Fall vorstellen , in dem Sie dies möglicherweise verursachen können. Hier ist ein analoges Beispiel in Basis 10 - das würde natürlich in Basis 2 passieren.

Gleitkommazahlen werden mehr oder weniger in wissenschaftlicher Notation gespeichert - das heißt, anstatt 35,2 zu sehen, würde die gespeicherte Zahl eher 3,52e2 entsprechen.

Stellen Sie sich der Einfachheit halber vor, wir haben eine Gleitkommaeinheit, die in Basis 10 arbeitet und eine Genauigkeit von 3 Stellen hat. Was passiert, wenn Sie 9,99 von 10,0 abziehen?

1.00e2-9.99e1

Verschieben, um jedem Wert den gleichen Exponenten zu geben

1.00e2-0.999e2

Auf 3 Stellen runden

1.00e2-1.00e2

Oh oh!

Ob dies letztendlich passieren kann, hängt vom FPU-Design ab. Da der Exponentenbereich für ein Double sehr groß ist, muss die Hardware irgendwann intern gerundet werden. Im obigen Fall verhindert jedoch nur eine zusätzliche Ziffer intern ein Problem.

Keldor314
quelle
1
Die Register, die die ausgerichteten Operanden zur Subtraktion enthalten, müssen zusätzliche zwei Bits enthalten, die als "Schutzbits" bezeichnet werden, um mit dieser Situation fertig zu werden. In dem Szenario, in dem die Subtraktion eine Ausleihe vom höchstwertigen Bit verursachen würde, muss entweder die Größe des kleineren Operanden die Hälfte der Größe des größeren Operanden überschreiten (was bedeutet, dass er nur ein zusätzliches Bit Genauigkeit haben kann), oder das Ergebnis muss mindestens sein die Hälfte der Größe des kleineren Operanden (was bedeutet, dass nur noch ein Bit benötigt wird, plus Informationen, die ausreichen, um eine korrekte Rundung sicherzustellen).
Supercat
1
„Ob dies letztendlich passieren kann, hängt vom FPU-Design ab.“ Nein, das kann nicht passieren, da die Java-Definition besagt, dass dies nicht möglich ist. Das FPU-Design hat nichts damit zu tun.
Pascal Cuoq
@PascalCuoq: Korrigieren Sie mich, wenn ich falsch liege, aber strictfpnicht aktiviert ist. Berechnungen können Werte liefern, die zu klein sind, doubleaber in einen Gleitkommawert mit erweiterter Genauigkeit passen.
Supercat
@supercat Das Fehlen von strictfpbeeinflusst nur die Werte von "Zwischenergebnissen", und ich zitiere aus docs.oracle.com/javase/specs/jls/se7/html/jls-15.html#jls-15.4 . aund bsind doubleVariablen, keine Zwischenergebnisse, daher sind ihre Werte Werte mit doppelter Genauigkeit, also Vielfache von 2 ^ -1074. Die Subtraktion dieser beiden Werte mit doppelter Genauigkeit ist folglich ein Vielfaches von 2 ^ -1074, so dass der breitere Exponentenbereich die Eigenschaft ändert, dass die Differenz 0 ist, wenn a == b.
Pascal Cuoq
@supercat Das macht Sinn - Sie würden nur ein zusätzliches Bit benötigen, um dies zu tun.
Keldor314
1

Sie sollten niemals Floats oder Doubles vergleichen, um die Gleichheit zu gewährleisten. weil Sie nicht wirklich garantieren können, dass die Nummer, die Sie dem Float oder Double zuweisen, genau ist.

Um Floats auf Gleichheit zu vergleichen, müssen Sie überprüfen, ob der Wert "nahe genug" an demselben Wert liegt:

if ((first >= second - error) || (first <= second + error)
aviad
quelle
6
"Sollte nie" ist ein bisschen stark, aber im Allgemeinen ist dies ein guter Rat.
Mark Pattison
1
Während Sie wahr sind, ist abs(first - second) < error(oder <= error) einfacher und prägnanter.
glglgl
3
Obwohl dies in den meisten Fällen ( nicht in allen Fällen ) der Fall ist, wird die Frage nicht wirklich beantwortet.
Milleniumbug
4
Das Testen von Gleitkommazahlen auf Gleichheit ist häufig nützlich. Es ist nicht vernünftig, mit einem Epsilon zu vergleichen, das nicht sorgfältig ausgewählt wurde, und noch weniger vernünftig, mit einem Epsilon zu vergleichen, wenn man auf Gleichheit prüft.
tmyklebu
1
Wenn Sie ein Array nach einem Gleitkommaschlüssel sortieren, kann ich garantieren, dass Ihr Code nicht funktioniert, wenn Sie versuchen, Gleitkommazahlen mit einem Epsilon zu vergleichen. Weil die Garantie, dass a == b und b == c a == c impliziert, nicht mehr da ist. Für Hash-Tabellen genau das gleiche Problem. Wenn Gleichheit nicht transitiv ist, brechen Ihre Algorithmen einfach.
Gnasher729
1

Die Division durch Null ist undefiniert, da die Grenze von positiven Zahlen gegen unendlich geht, die Grenze von negativen Zahlen gegen negative unendlich.

Ich bin mir nicht sicher, ob dies C ++ oder Java ist, da es kein Sprach-Tag gibt.

double calculation(double a, double b)
{
     if (a == b)
     {
         return nan(""); // C++

         return Double.NaN; // Java
     }
     else
     {
         return 2 / (a - b);
     }
}
Khaled.K
quelle
1

Das Kernproblem besteht darin, dass die Computerdarstellung eines Doppels (auch bekannt als float oder reelle Zahl in mathematischer Sprache) falsch ist, wenn Sie "zu viele" Dezimalstellen haben, z. B. wenn Sie mit double arbeiten, das nicht als numerischer Wert geschrieben werden kann ( pi oder das Ergebnis von 1/3).

A == b kann also nicht mit einem doppelten Wert von a und b gemacht werden. Wie geht man mit a == b um, wenn a = 0,333 und b = 1/3? Abhängig von Ihrem Betriebssystem gegen FPU gegen Anzahl gegen Sprache gegen Anzahl von 3 nach 0 haben Sie wahr oder falsch.

Wenn Sie auf einem Computer eine "Doppelwertberechnung" durchführen, müssen Sie sich mit der Genauigkeit befassen. Statt dies zu tun a==b, müssen Sie dies tun absolute_value(a-b)<epsilon, und epsilon ist relativ zu dem, was Sie zu diesem Zeitpunkt in Ihrem Algorithmus modellieren. Sie können nicht für alle Doppelvergleiche einen Epsilon-Wert haben.

Kurz gesagt, wenn Sie a == b eingeben, haben Sie einen mathematischen Ausdruck, der auf einem Computer nicht übersetzt werden kann (für jede Gleitkommazahl).

PS: Summen, alles, was ich hier beantworte, ist noch mehr oder weniger in anderen Antworten und Kommentaren enthalten.

Jean Davy
quelle
1

Basierend auf der Antwort von @malarres und dem Kommentar von @Taemyr ist hier mein kleiner Beitrag:

public double calculation(double a, double b)
{
     double c = 2 / (a - b);

     // Should not have a big cost.
     if (isnan(c) || isinf(c))
     {
         return 0; // A 'whatever' value.
     }
     else
     {
         return c;
     }
}

Mein Punkt ist zu sagen: Der einfachste Weg zu wissen, ob das Ergebnis der Division nan oder inf ist, ist tatsächlich die Division durchzuführen.

Orace
quelle