こんにちは！ペンすけです！
競プロに参加していたら、「Javaさんのバグか？」と思ってしまうような症状に苦しんだので記事に起こします。
（正確にはバグではなく、後述の浮動小数点計算の誤差によるものです）
社内システムやアプリでMath.powを使う場合、
システムエラーにならないよう、取り扱う値の範囲には十分注意してください！
\(10^{18}\)の計算を行った際にMath.powが壊れた
苦しむことになったのはこちらの問題です。
整数\(B\)が与えられて、それが\(N^N\)で表せるか判定する問題です！
解法としては、\(N = 1^1,~ 2^2,~ 3^3,~ \ldots \)と計算していき、\(B\)と一致するかif文で確かめる方法になります。
具体例
\(B = 256\) のとき、
\(1^1 = 1\)
\(2^2 = 4\)
\(3^3 = 27\)
\(4^4 = 256\) 一致！
と、\( 4^4 \) で表せる。
int型じゃなくてlong型にだけするのを忘れないようにすれば大丈夫でしょ！
と、意気揚々に実装しました。
実装したもの
// 整数Bの入力
long B = Long.parseLong(sc.next());
long num = 1;
long res = -1;
// ここで検証！！！
while(Math.pow(num, num) <= B){
if(Math.pow(num, num) == B){
res = num;
break;
}
num++;
}
// 結果の出力
if(res < 0){
// N^Nで表せない場合は-1
System.out.println(-1);
}
else{
System.out.println(res);
}結果はなんと「不正解」
(# ﾟДﾟ)ﾅﾝﾃﾞﾔﾈﾝ
元凶は浮動小数点の計算誤差
原因を探るべく\(N^N\)の結果を出力してみました。
すると、
1^1 = 1
2^2 = 4
3^3 = 27
4^4 = 256
5^5 = 3125
6^6 = 46656
7^7 = 823543
8^8 = 16777216
9^9 = 387420489
10^10 = 10000000000
11^11 = 285311670611
12^12 = 8916100448256
13^13 = 302875106592253
14^14 = 11112006825558016
15^15 = 437893890380859392\(15^{15}\)の1の位って必ず5になるはずじゃ…！
どうやらＭath.pow関数を使うと、\(10^{15}\)くらいから結果が怪しくなるようなので、
自作でpow関数を作って使うのが良いです。
private static long myPow(long base, long exp){
long res = 1;
for(long i=0; i<exp; ++i){
res *= base;
}
return res;
}15^15 = 437893890380859375
無事「正解」することができました。
浮動小数点の誤差は2進数↔10進数の変換で起こる誤差
いわゆる「丸め誤差」です。
情報処理技術者試験の経験がある方は「序盤に勉強したあれか！」となるかもしれません。
手元で検証してみます。
System.out.println(0.1);
System.out.println(new BigDecimal(0.1));このようなコードを書きました。BigDecimalというのは、限りなく正確な値を入れておくための型です。
どういうことかは次の結果を見るとわかります。
0.1
0.10000000000000000555...後ろの555…以降ってなに！？！
コンピューターは2進数で計算処理しています。
そのため、10進数と2進数の変換の際に、誤差が含まれてしまうことがあります。
通常は気にする程でもないですが、\(10^{15}\)のように桁数が大きい処理をしようとすると、その誤差が顕著に表れてしまいます。
まとめ
double型として処理するMath.pow等は、浮動小数点の誤差を引き起こす場合があります。
誤差を生じさせたくない場合は、int型やlong型等の整数型のみで実装をするか、BigDecimal型を使うと良いです。
誤差が含まれていることを知った上で、適切に使っていきましょう！
コメント