Ich habe dieses Problem aus dem Buch "Crack the Coding Interview".
Bestimmen Sie bei zwei Linien in einer kartesischen Ebene, ob sich die beiden Linien schneiden würden.
Hier ist die Lösung:
%Vor%Warum hat es nicht die einfache Lösung, dass, wenn die Steigungen nicht gleich sind, sie sich schneiden. Warum das Epsilon und das Y abfangen.
In den Vorschlägen heißt es, dass
Gehen Sie nicht davon aus, dass die Steigung und der y-Schnittpunkt ganze Zahlen sind. Verstehen Sie die Einschränkungen von Gleitkommadarstellungen. Niemals mit
==auf Gleichheit prüfen.
Die "Lösung" ist falsch.
Implizit in dieser "Lösung" ist eine Vorstellung, dass die übergebenen Argumente ungenau sind, dass, bevor intersect aufgerufen wird, die Werte Berechnungen unterzogen wurden, die Ergebnisse mit Rundungsfehlern erzeugen können. Da es in den Werten Fehler gibt, sind Zahlen, die bei genauem Berechnen gleich wären, ungleich. Um diese als gleich zu erkennen, akzeptiert diese "Lösung" einige tatsächlich ungleiche Werte als gleich.
Ein Fehler in dieser Argumentation besteht darin, dass die Routine intersect keine Kenntnis davon hat, wie groß die Fehler sein können, und daher keine Grundlage hat, zu wissen, welchen Wert von epsilon sie verwenden soll. Der ideale Wert könnte Null sein, oder es könnte eine Million sein. Der Wert, der verwendet wird, 1e-5, basiert aufgrund der bereitgestellten Informationen nicht auf einem technischen Prinzip. Mehr als das gibt es keine Grundlage für die Verwendung eines absoluten Fehlers, wie dieser Code tut. Abhängig von den Umständen kann die richtige Toleranz für die Verwendung ein relativer Fehler sein, ein Fehler, der in ULPs oder einer anderen Technik angegeben wird. Es gibt einfach keinen Grund zu der Annahme, dass dieser Code true zurückgibt, wenn Argumente übergeben werden, die idealerweise sich schneidende Linien darstellen, aber auf eine unbekannte Weise berechnet wurden.
Ein weiterer Fehler ist, dass die Routine fälschlicherweise als gleiche Werte akzeptiert, die nicht gleich sind. Die Routine meldet, dass sich nicht viele Linien überschneiden, die sich schneiden. Dieser Code hat das Problem der Routine, die die falsche Antwort zurückgibt, nicht gelöst; es hat nur die Fälle geändert, für die falsche Antworten zurückgegeben werden, und es hat möglicherweise die Anzahl der falschen Antworten stark erhöht.
Erstens, weil die einfache Lösung, wenn die Steigungen nicht die gleichen sind, die sie schneiden, nicht vollständig ist. Sie könnten dieselbe Steigung und denselben Schnittpunkt haben und wären daher identisch.
Das Epsilon, wie der Vorschlag sagt, ist, weil die Zahlendarstellung in Computern nicht genau ist. Laut dem IEEE-Standard hat ein Double etwa 15 präzise berechnete Stellen, daher können Steigung und Schnittpunkt einen Rundungsfehler haben zu vorherigen Berechnungen und daher könnte eine einfache Überprüfung mit == ergeben, dass sie nicht identisch sind, während sie sich nur durch einen Rundungsfehler unterscheiden.
Warum hat es nicht die einfache Lösung, wenn die Steigungen nicht sind gleich, dann werden sie sich schneiden. Warum das Epsilon und das Y abfangen.
Die Lösung berücksichtigt die Näherungsfehler aufgrund von Fließkomma Arithmetik. Da Fließkommazahlen nicht alle möglichen reellen Zahlen repräsentieren, sondern eine relativ kleine Teilmenge (dichter in [-1, + 1] Intervallen), ist es üblich, wenn Sie mit Gleitkommaarithmetik umgehen müssen, einen Schwellenwert zur Durchführung der Gleichheit zu verwenden überprüft.
Das epsilon valure repräsentiert einen Schwellenwert, unter dem 2 verschiedene Fließkommawerte als gleich betrachtet werden.
Darunter werden alle Zahlen bei der Verarbeitung in Binärwerte umgewandelt. Es ist nicht möglich, die meisten Fließkommazahlen als exakte Binärzahl darzustellen (weil sie eine unendliche Folge von 1en und 0en wären), und so werden Annäherungen gemacht, indem die binäre Sequenz abgeschnitten wird. Zum Beispiel ist die Gleitkommazahl 0,1 (dh ein Zehntel) nicht als exakte Binärzahl darstellbar, sondern wird durch eine Näherung dargestellt, die wie 0,000110011 aussieht ... Das Abschneiden dieser Binärzahl verursacht potentielle Rundungsfehler und so die exakte Gleichheit "==" könnte eine falsche Antwort verursachen, wenn es tatsächlich dieser Rundungsfehler ist, der das falsche Negativ gibt. Die Einführung eines Epsilons versucht, diese Fehler zu vermeiden, indem es sagt "alles, was unter dieser Zahl liegt, die wir für null halten". Weitere Informationen finden Sie im Abschnitt "Bruchteile im Binärformat" von wikipedia .
Tags und Links java math floating-point