C++で実装する高速逆平方根（Fast Inverse Square Root）アルゴリズムの解説

この問題では、整数 x が与えられ、それを32ビット浮動小数点数として扱い、高速逆平方根（Fast Inverse Square Root、すなわち 1/√x）を計算することを目的とします。

逆平方根を求めるこのアルゴリズムは、3Dグラフィックスにおけるベクトルの正規化など、特にコンピュータゲームのプログラミングにおいて絶大な効果を発揮する手法として知られています。名作FPS『Quake III Arena』のソースコードに採用されていたことから、「Quake IIIのアルゴリズム」としても広く知られています。

アルゴリズムの手順

ステップ1：浮動小数点値を、同じビットパターンを持つ整数値として解釈します。

ステップ2：その整数値に対して演算を行い、逆平方根の近似値を求めます。ここでは「マジックナンバー」と呼ばれる定数 0x5f3759df を使用します。

ステップ3：ステップ1と同じ方法を使って、整数値を再び浮動小数点値へと戻します。

ステップ4：ニュートン法（Newton's method）による反復計算を1回行い、近似精度をさらに向上させます。

なぜ高速に動作するのか

IEEE 754形式のfloatは、符号部・指数部・仮数部という構造を持っています。このビット列を整数として読み出すと、元の値の対数に近い値が得られるという性質があります。この性質を利用し、定数 0x5f3759df からビット列の半分を減算するだけで、逆平方根の良好な初期近似値を得ることができるのです。従来のように sqrt() を呼び出してから除算する方法と比べ、はるかに少ない演算量で処理できます。

アルゴリズムの動作を示すプログラム

例

#include<iostream>
using namespace std;

float calcInvSqRoot( float n ) {

    const float threehalfs = 1.5F;
    float y = n;

    long i = * ( long * ) &y;

    i = 0x5f3759df - ( i >> 1 );
    y = * ( float * ) &i;

    y = y * ( threehalfs - ( (n * 0.5F) * y * y ) );

    return y;
}

int main(){

    int n = 256;
    float invSqRoot = calcInvSqRoot(n);
    cout<<"The inverse square root of the number "<<n<<" is "<<invSqRoot;

    return 0;
}

出力

The inverse square root of the number 256 is 0.0623942

実際に 1/√256 = 0.0625 であることを考えると、わずか数ステップの演算で極めて近い近似値が得られていることがわかります。

注意点

この手法は1990年代後半の限られたハードウェア環境では画期的でしたが、現代のCPUには逆平方根用の最適化された命令（SSEの rsqrtss 命令など）が備わっており、コンパイラの最適化も高度です。そのため、現在の開発では通常、標準ライブラリの sqrt() や std::sqrt() を使用する方が安全かつ高速であり、このアルゴリズムは主に歴史的・教育的な価値を持つものといえます。