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の高速化なので、たくさん使用しないと気にならないレベルではある。

広告

コメントをどうぞ(承認された後に公開されます。メールアドレスの記入は自由ですが、記入した場合でも一般公開されることはありません)

以下に詳細を記入するか、アイコンをクリックしてログインしてください。

WordPress.com ロゴ

WordPress.com アカウントを使ってコメントしています。 ログアウト / 変更 )

Twitter 画像

Twitter アカウントを使ってコメントしています。 ログアウト / 変更 )

Facebook の写真

Facebook アカウントを使ってコメントしています。 ログアウト / 変更 )

Google+ フォト

Google+ アカウントを使ってコメントしています。 ログアウト / 変更 )

%s と連携中