JavaのMath.sqrtの誤差の落とし穴

#概要
あるプログラミングコンテストにおいて、JavaのMath.sqrtメソッドにおける誤差について、自分自身の反省も兼ねて、私自身がハマった落とし穴と、その回避方法をまとめました。

#対象
+ javaのバージョン:1.8

※ 他のバージョンでも、もっというと他の言語でもほぼ同じ挙動だと思いますが、一応このバージョンで動作確認をしていますので、念の為。

#はじめに
JavaのMathクラスのsqrtメソッドは、double型で与えられた数値の平方根を求めることができるメソッドで、数値計算を行う際などによく利用されます。

ただし、当然、結果には多少の誤差があります。

多くの場合、その結果は無視できる程度の小さなものとなりますが、時としてその誤差が無視できないものとなる場合があります。

この記事では、私が遭遇した事例についてご紹介し、その回避方法の例をご説明します。

#誤差が問題となった事例
私が参加した、あるプログラミングコンテストにおいて、以下のようなコードを書く必要が出てきました。
> $a \leq 10^{18}$を満たす正の整数$a$が与えられたとき、$b^{2} < a$を満たす$b$の最大値を求めたい。

#サンプルコード1
最初に私が書いたコードがこちらです。
（2018/4/9追記）なお、コメントでご指摘があったとおり、このコードは少々無駄があります。「サンプルコード訂正版」を末尾に追記致しました。

```java:sample1.java(抜粋)
    private static long floorSqrt (long a) {
        long b = (long)Math.sqrt(a);
        if (b*b == a) {
            return b-1;
        } else {
            return b;
        }
    }
```

簡単に説明します。

* $a$が、平方数（自然数の2乗に等しい数）の場合、<br>
--> 求める$b$は、$\sqrt{a}$ （=整数値）から1を引いた数です。
* $a$が、平方数でない場合、<br>
--> 求める$b$は、$\sqrt{a}$（=非整数値）の小数点以下を切り捨てた数です。

一見正しく動きそうですが、上記のコードは、正しく動きません。

#サンプルコード1の結果
（2018/4/9追記）なお、コメントでご指摘があったとおり、このコードは少々無駄があります。「サンプルコード訂正版」を末尾に追記致しました。

```java: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;
        }
    }
```
上記サンプルコードの実行結果は以下の通りです。

```text
lessThanSqrt (99)=9
lessThanSqrt  (100)=9
lessThanSqrt (999999999)=99999
lessThanSqrt  (10000000000)=99999
lessThanSqrt (999999999999999999)=1000000000
lessThanSqrt (1000000000000000000)=999999999
```
値が極端に大きくなった場合、結果がおかしくなっています。

# サンプルコード1の問題点
こうなった原因は以下のサンプルコードの実行結果を見ればわかります。

```java: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));
    }
}
```
実行結果

```text
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追記）なお、コメントでご指摘があったとおり、このコードは少々無駄があります。「サンプルコード訂正版」を末尾に追記致しました。

```java: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);
        // 得られた値を2乗して元の値を超える場合は
        // 誤差で1大きくなっているため
        // 誤差修正のため1引いた値を返す
        if(b*b > a) {
            b--;
        }
        return b;
    }
}
```
実行結果

```text
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追記）サンプルコード訂正版
サンプルコードの無駄な部分を、効率の良いコードに訂正したものを示しておきます。

```java:Sample1Modified.java(抜粋)
    private static long lessThanSqrt (long a) {
        return (long)Math.sqrt(a-1);
    }
```

```java:Sample2Modified.java(抜粋)
    private static long lessThanSqrt (long a) {
        return longSqrt(a-1);
    }
```

場合分けをしなくても、$\sqrt{aｰ1}$をとれば十分です。