In einem Programmierwettbewerb fasste ich die Fallstricke zusammen, denen ich verfallen war, und wie ich sie vermeiden konnte, sowie meine eigene Reflexion über die Fehler in Javas Math.sqrt-Methode.
Die sqrt-Methode der Java-Klasse Math ist eine Methode, mit der die Quadratwurzel eines durch den Doppeltyp angegebenen numerischen Werts ermittelt werden kann. Sie wird häufig bei der Durchführung numerischer Berechnungen verwendet.
Natürlich gibt es einige Unstimmigkeiten in den Ergebnissen.
In vielen Fällen ist das Ergebnis vernachlässigbar, in einigen Fällen ist der Fehler jedoch nicht vernachlässigbar.
In diesem Artikel zeige ich Ihnen einige der Fälle, auf die ich gestoßen bin, und gebe Beispiele, wie Sie sie vermeiden können.
Bei einem Programmierwettbewerb, an dem ich teilgenommen habe, musste ich den folgenden Code schreiben.
Bei einer positiven ganzen Zahl $ a $, die $ a \ leq 10 ^ {18} $ erfüllt, möchte ich den Maximalwert von $ b $ ermitteln, der $ b ^ {2} <a $ erfüllt.
Hier ist der Code, den ich zuerst geschrieben habe. (Hinzugefügt am 9. April 2018) Wie Sie in den Kommentaren betont haben, ist dieser Code etwas verschwenderisch. "Beispielcode korrigierte Version" wurde am Ende hinzugefügt.
sample1.java(Auszug)
private static long floorSqrt (long a) {
long b = (long)Math.sqrt(a);
if (b*b == a) {
return b-1;
} else {
return b;
}
}
Ich werde es kurz erklären.
Auf den ersten Blick scheint es zu funktionieren, aber der obige Code funktioniert nicht.
(Hinzugefügt am 9. April 2018) Wie Sie in den Kommentaren betont haben, ist dieser Code etwas verschwenderisch. "Beispielcode korrigierte Version" wurde am Ende hinzugefügt.
sample1.java
public class Sample1 {
public static void main(String[] args) {
System.out.println("lessThanSqrt (99)=" + lessThanSqrt (99));
System.out.println("lessThanSqrt (100)=" + lessThanSqrt (100));
System.out.println("lessThanSqrt (999999999)=" + lessThanSqrt (9999999999L));
System.out.println("lessThanSqrt (10000000000)=" + lessThanSqrt (10000000000L));
System.out.println("lessThanSqrt (999999999999999999)="+lessThanSqrt (999999999999999999L));
System.out.println("lessThanSqrt (1000000000000000000)=" + lessThanSqrt (1000000000000000000L));
}
private static long lessThanSqrt (long a) {
long b = (long)Math.sqrt(a);
if (b*b == a) {
return b-1;
} else {
return b;
}
}
Das Ausführungsergebnis des obigen Beispielcodes ist wie folgt.
lessThanSqrt (99)=9
lessThanSqrt (100)=9
lessThanSqrt (999999999)=99999
lessThanSqrt (10000000000)=99999
lessThanSqrt (999999999999999999)=1000000000
lessThanSqrt (1000000000000000000)=999999999
Wenn der Wert extrem hoch ist, ist das Ergebnis seltsam.
Die Ursache hierfür kann anhand des Ausführungsergebnisses des folgenden Beispielcodes verstanden werden.
sample1_1.java
public class Sample1_1 {
public static void main(String[] args) {
System.out.println(Math.sqrt(99999999999999L));
System.out.println(Math.sqrt(100000000000000L));
System.out.println(Math.sqrt(9999999999999999L));
System.out.println(Math.sqrt(10000000000000000L));
System.out.println(Math.sqrt(999999999999999999L));
System.out.println(Math.sqrt(1000000000000000000L));
}
}
Ausführungsergebnis
9999999.99999995
1.0E7
1.0E8
1.0E8
1.0E9
1.0E9
Betrachtet man die obigen Ergebnisse, so sind die Ergebnisse von $ \ sqrt {10 ^ {2n}} $ und $ \ sqrt {10 ^ {2n} -1} $ gleich, wenn $ n> 8 $. Ich bin.
Dies ist ein Problem mit der doppelten Genauigkeit.
Da für die Genauigkeit des Doppeltyps nur etwa 15 Stellen mit Informationen gespeichert werden können, ist es nicht möglich, Informationen mit einer größeren Anzahl von Stellen beizubehalten, was zu einem Fehler vom ursprünglichen Wert führt.
In den meisten Fällen ist der Effekt gering, aber wenn die Anzahl der Stellen im Bruchteil alle 9s beträgt, kann sich die Anzahl im Ganzzahlteil aufgrund eines Fehlers ändern.
Die obige Situation tritt wahrscheinlich auf, wenn die Quadratwurzel für eine große Zahl berechnet wird.
Unten finden Sie den Code, der die Probleme von Beispielcode 1 berücksichtigt und Logik hinzufügt, um den Fehler zu korrigieren. (Hinzugefügt am 9. April 2018) Wie Sie in den Kommentaren betont haben, ist dieser Code etwas verschwenderisch. "Beispielcode korrigierte Version" wurde am Ende hinzugefügt.
sample2.java
public class Sample2 {
public static void main(String[] args) {
System.out.println("lessThanSqrt (99)=" + lessThanSqrt (99));
System.out.println("lessThanSqrt (100)=" + lessThanSqrt (100));
System.out.println("lessThanSqrt (999999999)=" + lessThanSqrt (9999999999L));
System.out.println("lessThanSqrt (10000000000)=" + lessThanSqrt (10000000000L));
System.out.println("lessThanSqrt (999999999999999999)="+lessThanSqrt (999999999999999999L));
System.out.println("lessThanSqrt (1000000000000000000)=" + lessThanSqrt (1000000000000000000L));
}
private static long lessThanSqrt (long a) {
long b = longSqrt(a);
if (b*b == a) {
return b-1;
} else {
return b;
}
}
private static long longSqrt (long a) {
long b = (long)Math.sqrt(a);
//Wenn der erhaltene Wert quadratisch ist und den ursprünglichen Wert überschreitet
//Weil der Fehler 1 größer ist
//Gibt den Wert minus 1 zurück, um den Fehler zu korrigieren
if(b*b > a) {
b--;
}
return b;
}
}
Ausführungsergebnis
lessThanSqrt (99)=9
lessThanSqrt (100)=9
lessThanSqrt (999999999)=99999
lessThanSqrt (10000000000)=99999
lessThanSqrt (999999999999999999)=999999999
lessThanSqrt (1000000000000000000)=999999999
Sie können jetzt die richtigen Ergebnisse erhalten.
Im Allgemeinen ist es bei der Durchführung von Gleitkomma-Berechnungen erforderlich, Fehler zu berücksichtigen, die nicht auf + sqrt beschränkt sind. Wenn Sie mit Gleitkommatypen normalerweise nicht zu viel umgehen, werden Sie häufig die Überlegung verpassen. Seien Sie also vorsichtig.
Hier ist eine Korrektur des nutzlosen Teils des Beispielcodes zu einem effizienten Code.
Sample1Modified.java(Auszug)
private static long lessThanSqrt (long a) {
return (long)Math.sqrt(a-1);
}
Sample2Modified.java(Auszug)
private static long lessThanSqrt (long a) {
return longSqrt(a-1);
}
Es reicht aus, $ \ sqrt {a-1} $ zu nehmen, ohne den Fall zu teilen.
Recommended Posts