シフト演算とMath.pow(2, n)と（＋Math.pow(2, n)の怪）

自分が時々やらかしてしまうのでメモ。

環境は、CentOS 7(VM)上のOpenJDK 1.8.0_111。

2のべき乗(整数値)が欲しい場合はシフト演算

2のべき乗(整数値)が欲しいときに時々やらかしてしまうのが、以下のようなコードを書いてしまうこと。

for (int i = 0; i < 63; ++i) {
    long tmp = (long)Math.pow(2, i);
}

基数が2以外だったり指数が整数でなかったりdouble値が欲しかったりlongのMAX_VALUEを超える場合だったり、そんな場合は仕方がないのだが、2のべき乗(整数値)が欲しい場合はシフト演算の方が断然速い。

for (int i = 0; i < 63; ++i) {
    long tmp = 1L << i;
}

どれくらい速いのか、実際に計ってみた。

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        long S;
        long G;

        int cnt;

        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();

        System.out.print(n);

        S = System.currentTimeMillis();
        test1(n, m);
        G = System.currentTimeMillis();
        System.out.print("," + (G - S));

        S = System.currentTimeMillis();
        test2(n, m);
        G = System.currentTimeMillis();
        System.out.print("," + (G - S));

        S = System.currentTimeMillis();
        test3(n, m);
        G = System.currentTimeMillis();
        System.out.print("," + (G - S));

        System.out.println();
    }
    private static void test1(int n, int m) {
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < 63; ++j) {
                long tmp = 1L << j;
            }
        }
    }
    private static void test2(int n, int m) {
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < 63; ++j) {
                long tmp = (long)Math.pow(2, j);
            }
        }
    }
    private static void test3(int n, int m) {
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < 63; ++j) {
                long tmp = (long)Math.pow(2, m);
            }
        }
    }
}

test1が「Math.pow(2, n)」、test2が「シフト演算」を使ったケース。

test3は後で使うので後述。

実行は以下のような感じ。

for i in 100 250 500 1000 2500 5000 10000 25000 50000 100000 250000 500000 1000000 ; do
    echo $i 62 | java Main
done

実行結果のうち、test1とtest2を抜き出したものは以下の通り。単位はミリ秒。

n	test1	test2
100	0	1
250	0	2
500	0	3
1000	1	5
2500	3	16
5000	5	30
10000	9	54
25000	10	121
50000	12	233
100000	13	458
250000	21	1142
500000	31	2260
1000000	54	4513

全然違う。

Math.pow(2, n)の怪

検証している最中に妙なことに気付いたのでついでにメモ。

上記プログラムのtest1とtest3を使う。

test3のポイントは、「Math.pow(2, m)」とループの最中に変わることがない値を指数に指定していること。

実行結果のうち、test1とtest3を抜き出してみる。単位はミリ秒。

n	test1	test3
100	0	0
250	0	1
500	0	3
1000	1	8
2500	3	18
5000	5	31
10000	9	37
25000	10	37
50000	12	40
100000	13	45
250000	21	59
500000	31	83
1000000	54	130

それでもシフト演算の方が速いのだが、test2との違いは何だろう‥ソースを追おうにもnativeメソッドだし‥謎だ‥