はじめに
3DCGやシェーディング、ベクトル計算などの分野でしばしば必要になる「平方根の逆数（1/√x）」の計算。ゲームやグラフィックスプログラミングの世界では、単位ベクトルの正規化や法線計算、光の反射やベクトルの当たり判定など、高速な逆平方根計算が欠かせません。
そんな中で登場するのが「rsqrt関数」。シェーディング言語について調べてたら「Fast inverse square root」という有名な高速アルゴリズムがあることを知りました。このアルゴリズムは古くから知られ、特に『Quake III Arena』で使われたことで有名です。なお、日本語だと、井尻さんのサイトの高速根号計算 (fast sqrt algorithm)がすごく詳しい。
このページでは、Javaで高速に平方根の逆数を計算する方法と、その効果を実測した結果を紹介します。
Fast inverse square rootとは？
Fast inverse square rootは、以下の処理によって高速に1/√x を計算する手法です。
- 1回のビット演算
- 1回のニュートン法による近似
少し精度は落ちますが、「従来より3倍速い」という事例も報告されています。単位ベクトルの正規化やグラフィック計算など、膨大な回数呼び出す関数にとって、この速度差は大きな意味を持ちます。
Javaでの実装例
標準的な計算方法
普通にJavaの標準Math.sqrtを使った rsqrt1()
final public static float rsqrt1(float x) {
return((float)Math.sqrt(1f / x));
}
高速逆平方根アルゴリズム
こちらが高速アルゴリズム版 rsqrt2()
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);
}
数値 0x5f375a86（通称：マジックナンバー）を使うことで、最初の近似値を得て、ニュートン法で1回だけ補正しています。
ベンチマーク
実際にどれぐらい速度が上がるのか、最適化が行われないように注意して以下のようなコードで測定してみました。１回の計算速度を調査するのではなく、複数回実行した時の時間を、標準版と高速版とで比較して速度を調べる方法を取ります。
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+")");
}
実行結果
テスト環境：Windows7 64ビット, Java6(x64), Core 2 Quad Q6600
- rsqrt1（標準）
- 2.091605E-5ms (2823098.8)
- rsqrt2（高速法）
- 1.503850E-5ms (2821045.0) (-serverあり）
- 1.528678E-5ms (2821045.0) (-serverなし)
※実際の高速化量は環境やJavaのバージョン、JITコンパイラの最適化状況などで異なります。
たしかに約3割ほど高速化されていることを確認できました。精度は完全な Math.sqrt に劣りますが、4桁程度までなら十分正確。ただそもそも、「数マイクロ秒」レベルの違いなので、この関数を大量に使用した場合にのみ効果があると思われます。
おわりに
平方根の逆数は3DCGや物理エンジンなど“速さ”が求められる場面で重宝します。Fast inverse square rootは伝説的なアルゴリズムとして知られています。
誤差もあるため、速さに問題がある状況に陥ったときのみ手を出してみるといいかもしれません。
コメント