Mathの高速化を検証する

# Mathは本当に遅いのか
[色の距離（色差）を計算](http://qiita.com/shinido/items/2904fa1e9a6c78650b93)するときにちょっとだけ試してみたので，実際によくある（小手先）高速化手法でMathが速くなるのか検証してみた．

## 検証方法
JavaとAndroidで検証．
単純に実行時間を`System.nanoTime`で取得し，比較している．
検証順や検証タイミングで最適化がかかったりするので，何回か実行して落ち着いた値で比較している．
Javaの検証はIntel Xeon E5 3.5GHzのMac Pro，Androidの検証はQualcomm Snapdragon 800 MSM8974 2.2GHzのSO-02Fで試している．
従来のMathクラスと，実装したDMathクラスで比較した．
10万回実行して1回あたりの実行時間をnano秒で表示している．詳しい方法は一番下を参照．

# べき乗の高速化
べき乗を計算する`Math.pow()`は小数のべき乗もサポートしているせいもあってかやたら遅い．最近のJavaやAndroidでも遅いかどうか検証．

```java
    public static final double pow(double v, int n){
        double vv = v;
        for (int i = 1; i < n; i++) {
            vv *= v;
        }

        return vv;
    }
```

まずは2乗，n=2の場合から．

```zsh:Java
Math  : 48.35398
DMath : 49.00398
```

```zsh:Android
Math  : 1174.02609
DMath : 850.5849
```

となり，Androidの場合に効果有り．
n=5の場合は，

```zsh:Java
Math  : 119.70004
DMath : 49.93871
```

```zsh:Android
Math  : 1812.45263
DMath : 1155.4152
```

となり，両方で効果有り．
2乗の場合は最適化してるんでしょうかね．n=3でも両方で効果有りでした．
関数はfor文で書いているが，要は掛け算した方が速いということなので，nの2乗を計算するときにわざわざ`Math.pow()`を引っ張り出さずに`n*n`と書く方が速いし文字も少なくて済む．
5乗とかは`n*n*n*n*n`って書くと何乗してるのか分からないからfor文にする方がいいと思う．試してみたけど性能は変わらない．
後，当然だけど小数を何回も掛け算すると誤差が大きくなる．精度を求める場合は`Math.pow()`を使いましょう．


# hypotの高速化
ピタゴラスの定理で出てくる$\sqrt{a^2+b^2}$を計算するのが`Math.hypot()`．高速化してみた．

```java
    public static final double hypot(double a, double b){
        return Math.sqrt(a*a + b*b);
    }
```

高速化っていいながら単に書き換えただけです．まぁ，べき乗の部分を展開してはいますが．
で，結果．

```zsh:Java
Math  : 598.20226
DMath : 67.31029
```

```zsh:Android
Math  : 1586.08674
DMath : 1303.91898
```

という感じで両方で効果有り．
で，実はそれもそのはずでこの方法だと2乗したり足し算したりしたときにバッファオーバーフローすると計算できないし，そのときに丸め誤差が発生しちゃうので精度が落ちます．
まぁ，大きな値は使わないとか，そんな精密な値は必要無いとか，実用上問題無い場面で使ってください．

# toDegreeの高速化
よくラジアンを角度に変えるtoDegreeは自分で書いた方が速いっていうのを見るんだけどホントか？っていうことでやってみた．

```java
    private static final double toD = 180.0 / Math.PI;
    public static final double toDegrees(double rad){
        return rad * toD;
    }
```

で，**ぶっちゃけMath.javaを読むとほぼ同じことが書いてある**のでやる意味無いと思うんだけど，staticに変数計算してるからワンチャンあるかも・・・！？（最適化されてるはずだけど）

```zsh:Java
Math  : 52.03437
DMath : 52.4816
```

```zsh:Android
Math  : 1065.92847
DMath : 1057.95507
```

はい，効果ありませんでした．Androidが勝ってるように見えるけれど，場合によっては逆転してるのでただの計測誤差です．

# 三角関数の高速化（近似）
三角関数は非常に遅いので，あらかじめメモリに計算結果を展開しておいて，メモリアクセスさせる方が速いっていうのは割と昔から知られている手法なんだけど，Cでベタに書くならまだしもJavaでそんなことやって速くなるのかな？っていうことでやってみました．

```java
    private static final int NUM = 1000;
    private static final double[] sinMap;

    static {
        sinMap = new double[NUM];
        for (int i = 0; i < NUM; i++) {
            sinMap[i] = Math.sin((double) i / NUM * Math.PI * 2);
        }
    }

    public static final double sin(double t){
        t = t / (Math.PI * 2) * NUM;
        return sinMap[ ((int) t ) % NUM];
    }
```

NUMが粒度で値を大きくするほど誤差が小さくなります．で，結果．

```zsh:Java
Math  : 104.53175
DMath : 60.14656
```

```zsh:Android
Math  : 1016.11446
DMath : 1028.96237
```

ということで意外にもJavaでは効果あり，Androidで効果無し．昔この手のことをAndroidでやったら無茶苦茶速くなったんだけど，実装が変わったんでしょうね．cosとかtanは省略，atanはちょっと方法が思いつかなかったです．

# sqrtの高速化（近似）
sqrtは1から近い領域でほとんど線形なので近似できます．まぁ，使用範囲が限られちゃいますが．

```java
    public static final double sqrt(double v){
        return 1d * ( v - 1d) / 2d;
    }
```

で，結果．

```zsh:Java
Math  : 50.19401
DMath : 50.36254
```

```zsh:Android
Math  : 1009.85237
DMath : 999.24091
```

はい，効果無し．

# roundの高速化
四捨五入するときに使う`Math.round()`ですがMath.javaを見ると精度を出すために結構面倒くさい作りになってます．てことで簡単に作り直してみたのが以下の実装．

```java
    public static final long round(double v){
        long l = (long) (v * 2);
        return (l >> 1) + (l & 0x1);
    }
```

要は2倍して奇数になるんだったら繰り上げときゃいいよね，という感じです．doubleを2倍するとこは工夫するともうちょい速く出来そうですが大した効果なさそうなのでこのままで．で，結果．

```zsh:Java
Math  : 50.90829
DMath : 49.94111
```

```zsh:Android
Math  : 1396.44914
DMath : 1016.95906
```

てことで，Javaは効果なし，Android効果有り・・・としたいんですが，Javaは何回やっても僅差で勝つので，効果あり・・・！ということにしといてください．
当然，2倍したりしてるので使える値はLong.MAXVALUEの半分までです．まぁ，足りますよね．
ceilとfloorは使用用途によってはintにキャストしたりするだけで事が足りそうなので省略．精度を出すにはやっぱりちゃんとMathを使ってください．

# おわり
ネタ切れにつき終わり．
全ての方法について言えることですが，例えばNaNとかInfinityが突っ込まれたときの処理は無視しています．if文が増えるぐらいなので性能に影響は無さそうですが，使う側はその辺を理解して使ってください．
後，「JNIした方が速いんじゃないの？」という突っ込みは無しの方向でお願いします．

# おまけ
検証用のソースは下記の通り．

```java
    public static final void task(String name, int num, MathTask math, MathTask dmath){
        long start;
        long mathTime = 0;
        long dmathTime = 0;

        for(int i = 0; i < num; i++){
            start = System.nanoTime();
            math.task(rand);
            mathTime += (System.nanoTime() - start);

            start = System.nanoTime();
            dmath.task(rand);
            dmathTime += (System.nanoTime() - start);
        }

        double mathResult = ((double) mathTime) / num;
        double dmathResult = ((double) dmathTime) / num;

        System.out.println("Math  : " + mathResult);
        System.out.println("DMath : " + dmathResult);
    }
```

MathTaskクラスは引数にRandomを受け取るメソッドが1つだけのインタフェースでlambda的に書くために定義した．`task(... (r)->Math.abs(r.nextInt()), ...)`みたいにして使用する．一応確認したが，こういった抽象化による実行時間への影響は見られなかった．
numに10万を指定して10万回の平均値を取っている．また，Androidでは10回同じ事を繰り返して落ち着いてきた値（3回ぐらい同じ結果が出てきたあたり）を掲載した．
JavaもAndroidも一番最初が一番遅く，何回も試行すると速くなってくるので何かしらの最適化が効いているんだと思う．（GCは動いてないっぽい）