概要
あるプログラミングコンテストにおいて、JavaのMath.sqrtメソッドにおける誤差について、自分自身の反省も兼ねて、私自身がハマった落とし穴と、その回避方法をまとめました。
対象
- javaのバージョン:1.8
※ 他のバージョンでも、もっというと他の言語でもほぼ同じ挙動だと思いますが、一応このバージョンで動作確認をしていますので、念の為。
はじめに
JavaのMathクラスのsqrtメソッドは、double型で与えられた数値の平方根を求めることができるメソッドで、数値計算を行う際などによく利用されます。
ただし、当然、結果には多少の誤差があります。
多くの場合、その結果は無視できる程度の小さなものとなりますが、時としてその誤差が無視できないものとなる場合があります。
この記事では、私が遭遇した事例についてご紹介し、その回避方法の例をご説明します。
誤差が問題となった事例
私が参加した、あるプログラミングコンテストにおいて、以下のようなコードを書く必要が出てきました。
$a \leq 10^{18}$を満たす正の整数$a$が与えられたとき、$b^{2} < a$を満たす$b$の最大値を求めたい。
サンプルコード1
最初に私が書いたコードがこちらです。
（2018/4/9追記）なお、コメントでご指摘があったとおり、このコードは少々無駄があります。「サンプルコード訂正版」を末尾に追記致しました。
private static long floorSqrt (long a) {
long b = (long)Math.sqrt(a);
if (b*b == a) {
return b-1;
} else {
return b;
}
}
簡単に説明します。
- $a$が、平方数（自然数の2乗に等しい数）の場合、
--> 求める$b$は、$\sqrt{a}$ （=整数値）から1を引いた数です。 - $a$が、平方数でない場合、
--> 求める$b$は、$\sqrt{a}$（=非整数値）の小数点以下を切り捨てた数です。
一見正しく動きそうですが、上記のコードは、正しく動きません。
サンプルコード1の結果
（2018/4/9追記）なお、コメントでご指摘があったとおり、このコードは少々無駄があります。「サンプルコード訂正版」を末尾に追記致しました。
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;
}
}
上記サンプルコードの実行結果は以下の通りです。
lessThanSqrt (99)=9
lessThanSqrt (100)=9
lessThanSqrt (999999999)=99999
lessThanSqrt (10000000000)=99999
lessThanSqrt (999999999999999999)=1000000000
lessThanSqrt (1000000000000000000)=999999999
値が極端に大きくなった場合、結果がおかしくなっています。
サンプルコード1の問題点
こうなった原因は以下のサンプルコードの実行結果を見ればわかります。
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));
}
}
実行結果
9999999.99999995
1.0E7
1.0E8
1.0E8
1.0E9
1.0E9
上記の結果を見ると、$n > 8$の場合、$\sqrt{10^{2n}}$と、$\sqrt{10^{2n}-1}$の結果が同じ値になってしまっています。
これはdouble型の精度の問題となります。
double型の精度としては、約15桁ほどの情報しか保持できないため、それより大きな桁数情報を保持することができず、本来の値との誤差が生じます。
ほとんどの場合は影響が小さいのですが、小数部の桁がすべて9が続いているような数値の場合、誤差によって、整数部の数値が変わってしまうことがあります。
大きな数に対する平方根の計算では、上記のような状況が生じやすくなります。
サンプルコード2
サンプルコード1の問題点を考慮し、誤差を修正するロジックを追加したコードが下記のとおりです。
（2018/4/9追記）なお、コメントでご指摘があったとおり、このコードは少々無駄があります。「サンプルコード訂正版」を末尾に追記致しました。
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);
// 得られた値を2乗して元の値を超える場合は
// 誤差で1大きくなっているため
// 誤差修正のため1引いた値を返す
if(b*b > a) {
b--;
}
return b;
}
}
実行結果
lessThanSqrt (99)=9
lessThanSqrt (100)=9
lessThanSqrt (999999999)=99999
lessThanSqrt (10000000000)=99999
lessThanSqrt (999999999999999999)=999999999
lessThanSqrt (1000000000000000000)=999999999
正しい結果が得られるようになりました。
まとめ
- 整数を扱う問題でsqrtを使う場合、上記のような誤差にご注意ください。
補足・雑記
- sqrtに限らず、一般的に浮動小数点型の計算をする場合は、誤差に対する配慮が必要となります。普段、浮動小数点型を余り扱わない場合、配慮が漏れがちになるので、要注意となります。
- Mathクラスのメソッドは、ほとんどdouble型を扱うことになりますので、誤差に要注意となります。バグの温床にもなりますので、整数しか扱わない問題の場合、int、longだけで組めれば一番良いと思います（誤差を気にしなくていいですし、処理速度も早くなる事が多いので）。
- Mathクラスのメソッドについて、整数だけで実装できないかを考えてみるのも、アルゴリズムの勉強にいいかもしれません。
（2018/4/9追記）サンプルコード訂正版
サンプルコードの無駄な部分を、効率の良いコードに訂正したものを示しておきます。
private static long lessThanSqrt (long a) {
return (long)Math.sqrt(a-1);
}
private static long lessThanSqrt (long a) {
return longSqrt(a-1);
}
場合分けをしなくても、$\sqrt{aｰ1}$をとれば十分です。