シェーディング言語について調べてたら
平方根の逆数を高速に求める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の高速化なので、たくさん使用しないと気にならないレベルではある。
コメント