難解なDouble
他の言語: English Español 한국어 Português 中文
あなたはすでに知っているのではないでしょうか:
double データ型はあまり精度が高くない
この理解を深めるために、CodeWarsの問題を解くことにしましょう。
問題の説明
CodeWarsで述べられている課題は以下の通りです：
あなたの課題は、n 個の立方体の積み重ねである建物を建設することです。 下部の立方体の体積は n^3、その上の立方体の体積は (n-1)^3、 そして最上部の立方体の体積は 1^3 となります。
あなたには、建物の合計体積 m が与えられます。 m を与えられた場合、あなたは立方体をいくつ建設しなければならないのか、 その数 n を見つけることができますか？
関数 findNb のパラメータは整数の m であり、
もし存在するならば n^3 + (n-1)^3 + … + 1^3 = m となる数値 n を返すか、
そのような n が存在しない場合は -1 を返す必要があります。
単純な解法
最も直感的なループを使用した解法は次のようなものです：
public static long findNb(long m) {
long n = 0, totalVolume = 0;
while (totalVolume < m) {
totalVolume += ++n * n * n;
}
return totalVolume == m ? n : -1;
}数学的な解法
大学のときに数学的な級数とその和を計算する方法について学んだので、 数学的な解法について提案してみます。
式はもう覚えていませんが、ありがたいことにWolfram Alphaが助けてくれます。 その式を得るために次のクエリを実行してみましょう: n^3, n = 1 to k。
結果は次のとおりです:
等式の左側に m を代入し、次に平方根の性質を適用し、
等式の両辺を2で乗じてみます。それを簡略化すると：
コードを書く
以下に示すのは、上記の等式を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;
}結果
このコードは、テストデータの一部のサブセットに対して誤った結果を返すことが判明しました。
この不一致は、例えば、入力として 1646842954019151682L を渡したときに判明します。
Javaで平方根を計算する際、結果が完全に正確でない場合があります。例を見てみましょう：
System.out.println(String.format("%.30f", Math.sqrt(1646842954019151682L)));
// output 1283293791.000000000000000000000000000000
// correct 1283293791.00000000038962239473657673134031176401122912...明らかに、出力と正しい答えは異なっています。以上です！
結論
技術的に正確で潜在的に最も高速な解決策が常に最善の選択肢ではないです。 これは経験豊富な開発者にとっては驚くべきことではないかもしれませんが、プログラミング初心者にとっては、 このエラーの原因についてかなり頭を悩ませるかもしれません。
数学的な解法の問題をどのように解決すればいいのか疑問に思っている方のために、
一つのアプローチとして BigDecimal を使用する方法があります。このコードは全てのテストをパスします：
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;
}… そして小さなボーナス：次のうちどれが true で、どれが false でしょうか？
(1646842954019151681L == 1646842954019151682D)(1646842954019151681L == (long) 1646842954019151682D)
