Tueckisches Double
Andere Sprachen: English Español Français 日本語 한국어 Português 中文
Dieser Text ist eine Uebersetzung des Originalartikels von meinem Freund Maksim Pelevin. Wenn du Russisch lesen kannst, findest du moeglicherweise weitere interessante Artikel in seinem Blog.
Der double -Datentyp ist nicht sehr praezise
Vertiefen wir dieses Verstaendnis, indem wir ein Problem auf CodeWars loesen.
Problemstellung
Die Aufgabe, wie auf CodeWars beschrieben, lautet wie folgt:
Deine Aufgabe ist es, ein Gebaeude zu konstruieren, das aus einem Stapel von n Wuerfeln besteht. Der Wuerfel unten hat ein Volumen von n^3, der Wuerfel darueber hat ein Volumen von (n-1)^3 und so weiter bis zur Spitze, die ein Volumen von 1^3 hat.
Dir wird das Gesamtvolumen m des Gebaeudes gegeben. Kannst du bei gegebenem m die Anzahl n der Wuerfel finden, die du bauen musst?
Der Parameter der Funktion findNb ist eine ganze Zahl m
und du musst die ganze Zahl n zurueckgeben, sodass
n^3 + (n-1)^3 + … + 1^3 = m, wenn ein solches n existiert, oder -1, wenn es kein solches n gibt.
Naive Loesung
Die einfachste Loesung mit Schleifen waere so etwas wie:
public static long findNb(long m) {
long n = 0, totalVolume = 0;
while (totalVolume < m) {
totalVolume += ++n * n * n;
}
return totalVolume == m ? n : -1;
}Mathematische Loesung
An der Universitaet habe ich etwas ueber mathematische Reihen und die Methoden zur Berechnung ihrer Summen gelernt, also hier ist mein Ansatz fuer eine mathematische Loesung.
Ich erinnere mich nicht mehr an die Formeln, aber gluecklicherweise ist Wolfram Alpha da, um zu helfen. Um die Formel zu erhalten, fuehren wir die folgende Abfrage aus: n^3, n = 1 to k.
Die Ergebnisse sagen uns:
Setzen wir m fuer die linke Seite der Gleichung ein,
wenden dann die Quadratwurzeleigenschaft an
und multiplizieren beide Seiten der Gleichung mit zwei.
Nach Vereinfachung erhalten wir:
Schreibe den Code
Hier ist eine Loesung fuer die obige Gleichung, geschrieben in Java:
public static long findNb(long m) {
double res = Math.sqrt(m);
double d = 1 + 8 * res;
double n = (Math.sqrt(d) - 1) / 2;
return n - Math.floor(n) == 0 ? (long) n : -1;
}Ergebnisse
Es stellt sich heraus, dass dieser Code fuer eine Teilmenge der Testdaten ein falsches Ergebnis liefert.
Diese Inkonsistenz ist beispielsweise sichtbar, wenn
du 1646842954019151682L als Eingabe uebergibst.
Bei der Berechnung einer Quadratwurzel in Java kann man ein Ergebnis erhalten, das nicht vollstaendig genau ist. Schauen wir uns das an:
System.out.println(String.format("%.30f", Math.sqrt(1646842954019151682L)));
// output 1283293791.000000000000000000000000000000
// correct 1283293791.00000000038962239473657673134031176401122912...Offensichtlich sind die Ausgabe und die richtige Antwort unterschiedlich. Fin!
Fazit
Die technisch korrekteste und potenziell schnellste Loesung ist nicht immer die beste Wahl. Das mag fuer einen erfahrenen Entwickler keine Ueberraschung sein, aber Programmieranfaenger koennten eine Weile ueber die Ursache des Fehlers raetseln.
Falls du dich fragst, wie man das Problem mit der mathematischen Loesung beheben kann,
ein Ansatz ist die Verwendung von BigDecimal . Dieser Code besteht alle Tests:
public static long findNb(long m) {
MathContext mc = new MathContext(64);
BigDecimal res = BigDecimal.valueOf(m).sqrt(mc);
BigDecimal d = res.multiply(BigDecimal.valueOf(8)).add(BigDecimal.ONE);
BigDecimal n = d.sqrt(mc).subtract(BigDecimal.ONE).divide(BigDecimal.valueOf(2));
return Objects.equals(n, n.setScale(0, RoundingMode.FLOOR)) ? n.longValue() : -1;
}… und ein kleiner Bonus: Kannst du erraten, welches der folgenden true ist
und welches false ?
(1646842954019151681L == 1646842954019151682D)(1646842954019151681L == (long) 1646842954019151682D)
