GeeksforGeeks

高速逆平方根は、IEEE754浮動小数点形式の32ビット浮動小数点数xの平方根の逆数（または乗法逆数）であるを推定するアルゴリズ 逆平方根の計算は、ビデオゲームのベクトル正規化など、多くのアプリケーションで必要であり、主に3Dプログラミングに関わる計算に使用されます。 3Dグラフィックスでは、照明と反射を表現するために、長さ1の3座標ベクトルであるサーフェス法線が使用されます。 表面法線がたくさんありました。 それらを計算するには、多くのベクトルを正規化する必要があります。 正規化は、多くの場合、分割のための単なる派手な用語です。 ピタゴラスの定理は点間の距離を計算し、距離で除算するとベクトルを正規化するのに役立ちます:

このアルゴリズムは、3Dグラフィックスを多用した一人称シューティングゲームであるQuake III Arena Gameのソースコードで1999年に実装されたことで最もよく知られている。 当時、特に大規模な浮動小数点数の逆数を計算するのは一般的に計算コストがかかりました; 高速逆平方根は、このステップをバイパスしました。

アルゴリズム：
ステップ1：浮動小数点入力のビットを整数として再解釈します。ステップ2：結果の値を取得し、整数演算を行い、探している値の近似値を生成します。ステップ3：結果は近似そのものではありませんが、ビットを浮動小数点数として再解釈すると、近似が発生する整数です。 したがって、コードはステップ1の変換の逆を行い、浮動小数点に戻ります:

y = * ( float * ) &i;

ステップ4：そして最後に、近似を改善するためにNewtonの方法の単一の反復を実行します。

y = y * ( threehalfs - ( x2 * y * y ) ); //threehalfs = 1.5F;

アルゴリズムは入力として32ビット浮動小数点数を受け入れ、後で使用するために半分の値を格納します。 次に、浮動小数点数を表すビットを32ビット整数として処理し、論理シフトを1ビット右に行い、結果をマジックナンバー0x5f3759dfから減算します。 これは、入力の逆平方根の最初の近似です。 ビットを再び浮動小数点数として扱うと、ニュートンの近似法の反復が1回実行され、より正確な近似が得られます。

指数形式または科学表記法で数値があるとしましょう:
=100 million
さて、通常の平方根を見つけるために、指数を次のように除算します2:

逆平方根を知りたい場合は、指数を-2で除算して符号を反転します:

したがって、コードは浮動小数点数を整数に変換します。 これは、指数ビットが2で除算されることを意味します（最終的にビットを浮動小数点数に戻すとき）。 そして最後に、指数を否定するために、マジックナンバー0x5f3759dfから減算します。 これはいくつかのことを行います：仮数（非指数部、別名5）を保存します: 5 · ), 奇数-偶数の指数を処理し、指数から仮数にビットをシフトし、あらゆる種類のファンキーなものを処理します。

次のコードは、Quake III Arena（Quake III Arenaゲームで書かれた正確なオリジナルのコメント）からの高速逆平方根の実装です。

出力：