Quakeの高速逆平方根を理解する
記事と研究論文は、ゲームQuakeで使用される逆平方根（1 1/\sqrt{x}.）を計算するための高速で、一見魔法のような方法を説明しています。
私はグラフィックの専門家ではありませんが、平方根が有用な理由に感謝しています。 ピタゴラスの定理は点間の距離を計算し、距離で除算するとベクトルを正規化するのに役立ちます。 （正規化は、多くの場合、分割のための単なる派手な用語です。)
Quakeのような3Dゲームは、毎秒の距離ジリオン（はいジリオン）で除算するので、”マイナーな”パフォーマンスの改善は非常に役立ちます。 私たちは平方根を取って通常の方法を分割したくありません：べき乗と除算は本当にCPUにとって本当に高価です。
これらの条件を考えると、Quake（私のコメントが挿入されている）にあるように、Quake1/\sqrt{x}.を得る魔法の式があります：
私の理解：この信じられないほどのハ
推測を行うには、科学表記法で浮動小数点数を取り、&を否定して指数を半分にして逆平方根に近いものにします。 その後、推定値をさらに洗練するためにニュートンの近似法のラウンドを実行し、多田、我々は逆平方根の近くに何かを持っています。
ニュートンの近似法
ニュートンの方法は、任意の関数の近似根を見つけるために使用することができます。 ルートに近づくためにメソッドを反復し続けることができますが、この関数は1ステップしか使用しません！ ここではニュートンの方法のクラッシュコースです（それは私には新しいものでした):
あなたはこのプロセスを繰り返し続けることができます（あなたの新しい推測を式に差し込む）そしてあなたの根のためのより近い近似を得るこ 最終的には、f（新しい推測）を本当に、本当にゼロに近づける”新しい推測”があります-それは根です！ （または彼らが言うように、政府の仕事のために十分に近い）。
明らかに、私たちはエラーをできるだけ小さくしたいと思っています。 これは、誤差（x）=0になる”x”を見つけることを意味し、これは誤差方程式の根を見つけることと同じです。 誤差(x)をニュートンの近似式に代入すると:
そして、適切な導関数を取る:
私たちはそれらをプラグインして、より良い推測のための式を得ることができます:
これは、xが新しい推測（g）であり、”xhalf”が元の値（$0.5i）の半分であることを覚えておいて、上記のコードで見られる方程式です$):
x = x*(1.5f - xhalf*x*x);
この式を使用すると、推測”g”から始めて、より良い推測を得るために式を繰り返すことができます。 複数の反復を使用して逆二乗を見つけるためのこのデモを試してみてください：
だから私の友人は、質問になります：”どのように我々は良い初期推測を”
良い推測をする
逆平方根の良い推測は何ですか？ それはトリックの質問のビットです-逆平方根のための私たちの最高の推測は、逆平方根自体です！
ok hotshot、あなたは実際にactually1/\sqrt{x}xを得るにはどうすればよいですか？
ここで魔法が発動する。 指数形式または科学表記法の数値があるとしましょう:
さて、通常の平方根を見つけたい場合は、指数を次のように除算します2:
逆平方根が必要な場合は、指数を-2で除算して符号を反転します:
では、他の高価な操作なしで数値の指数を取得するにはどうすればよいですか？
浮動小数点数は仮数指数形式で格納されます
まあ、私たちは運がいいです。 浮動小数点数は仮数指数形式でコンピュータによって格納されるので、指数を抽出して分割することが可能です！
しかし、明示的に除算を行うのではなく（CPUには高価です）、コードは別の巧妙なハックを使用します：ビットをシフトします。 1つの位置で右シフトすることは、2で割ることと同じです（2の任意の累乗に対してこれを試すことができますが、残りは切り捨てられます）。 そして、負の数を取得したい場合は、-1を掛ける代わりに（乗算は高価です）、”0″から数を減算するだけです（減算は安いです）。
だから、コードは浮動小数点数を整数に変換します。 これは、指数ビットが2で除算されることを意味します（最終的にビットを浮動小数点数に戻すとき）。 そして最後に、指数を否定するために、マジックナンバー0x5f3759dfから減算します。 これはいくつかのことを行います：仮数（非指数部、別名5：$5\cdot10^6in）を保持し、奇数-偶数の指数を処理し、指数から仮数にビットをシフトし、あらゆる種類のフ 紙には詳細と説明がありますが、私は初めてそれをすべてキャッチしませんでした。 いつものように、あなたが何が起こっているのかのより良い説明があればコメントして自由に感じます。
結果は、実際の逆平方根に本当に近い最初の推測を得ることです！ その後、推測を洗練するためにニュートンの方法の単一のラウンドを行うことができます。 より多くのラウンドが可能です（追加の計算費用で）が、必要な精度のために必要なのは1ラウンドだけです。
だから、なぜマジックナンバー？
偉大なハックは、整数と浮動小数点数がどのように格納されているかです。 $5のような浮動小数点数。4\cdot10^6expon指数を”5.4″とは別の範囲のビットに格納します。 数値全体をシフトすると、指数を2で除算し、数値（5.4）を2で除算します。 これは魔法の数が入るところです-それは私がかなり理解していないこの部門のためのいくつかのクールな修正を行います。 しかし、使用できるマジックナンバーがいくつかあります-これは仮数の誤差を最小限に抑えるために起こります。
マジックナンバーは偶数/奇数の指数も修正していますが、この論文では、使用する他のマジックナンバーも見つけることができます。
リソース
reddit（ユーザー pb_zeppelin）とslashdotについてのさらなる議論があります:
- http://games.slashdot.org/article.pl?sid=06/12/01/184205 そして、私のコメント
このシリーズの他の投稿
- 数システムとベース
- Guidへのクイックガイド
- Quakeの高速逆平方根を理解
- コンピュータネットワーキングシンプルな紹介
- XORを使用して二つの変数を交換
- 大きくて小さな理解
- エンディアンバイトオーダー
- unicodeとあなた
- バイナリファイル形式について少しDiddy
- ソートアルゴリズム