Javaで高速に平方根の逆数を求める

アルゴリズム
スポンサーリンク

シェーディング言語について調べてたら
平方根の逆数を高速に求めるrsqrt関数というのがあるらしいことが分かった。

それで、この rsqrt について調べてたら、Fast inverse square rootっていう高速に計算できる記事を見つけた。
日本語だと、井尻さんのサイトの高速根号計算 (fast sqrt algorithm)がすごく詳しい。

このアルゴリズムを用いると、少し精度は落ちるが、高速に計算できるという。
3倍近く早くなったというサイトも見つけた。
逆平方根は、単位ベクトルを作成するときに必要であり、
3DCGの光の反射の計算、法線ベクトルの計算、ベクトルの当たり判定に欠かせないものとなる。
そこで、高速性を優先するなら、上記のアルゴリズムを用いるといいというわけである。

Javaでは実際にどれぐらい速度が上がるか調べてみた。
環境は「Windows7 64ビット Java6(x64)の最新版 Core 2 Quad Q6600」

次の関数を用意して比べてみる。

final public static float rsqrt1(float x) {
	return((float)Math.sqrt(1f / x));
}

final public static float rsqrt2(float x) {
	float half = 0.5f * x;
	x = Float.intBitsToFloat((0x5f375a86 - (Float.floatToIntBits(x) >>> 1)));
	x *= 1.5f - half * x * x;
	return(x);
}

main関数はこちら。
最適化が行われないように注意して書いてみた。

public static void main(String[] args) {
	long st,en,max = Long.MAX_VALUE;
	float x = 0f;
	Random random = new Random(0);
	for(int i = 0;i < 1000;i++) {
		float y = random.nextFloat();
		st = System.nanoTime();
		for(int j = 0;j < 100000;j++) {
			y += rsqrt2(y);
		}
		en = System.nanoTime();
		x += y;
		st = en - st;
		if(st < max) {
			max = st;
		}
		Log.sleep(10);
	}
	System.out.println((max / 1000000d / 100000d) + "ms" + " ("+x+")");
}

で結果
rsqrt1の場合は「2.091605E-5ms (2823098.8)」
rsqrt2の場合は「1.503850E-5ms (2821045.0)」(-serverあり) 「1.528678E-5ms (2821045.0)」(-serverなし)
数値は、大体1回にかかる時間。
4ケタまでは大体正しいのがでている。

一応少しばかり早い。
最初、適当なテストコード書いたら、
rsqrt2のほうがrsqrt1の3倍時間かかったけど、
これは最適化があったせいだったのかもしれない。

ただ高速化といっても1回あたり、
0.000005msの高速化なので、たくさん使用しないと気にならないレベルではある。

コメント

タイトルとURLをコピーしました