Quake IIIの高速逆平方根（0x5f3759df）

何のコードか

3D描画ではベクトルを長さ1に揃える「正規化」が絶え間なく必要で、各成分を長さ sqrt(x*x+y*y+z*z) で割ります。素直に書くと平方根と除算という当時のCPUで最も重い演算が要り、1フレームに何万回も走ります。Quake III Arena（1999年）のソースはこれを驚くべき方法で潰しました。それが Q_rsqrt、いわゆる高速逆平方根（fast inverse square root）です。有名になった理由は3つ。平方根も除算も使わず整数減算とビットシフトと少数の乗算だけで 1/sqrt(x) を誤差0.2%未満で返すこと、唐突な魔法定数 0x5f3759df とその投げやりなコメント、そしてこれほど有名なのに長年「誰が書いたのか」が不明だったことです。

コードと仕組みの解説

横にスクロール

公開されたコードはほぼ次のとおりです（コメントも原文どおり）。

float Q_rsqrt( float number )
{
	long i;
	float x2, y;
	const float threehalfs = 1.5F;

	x2 = number * 0.5F;
	y  = number;
	i  = * ( long * ) &y;                       // evil floating point bit level hacking
	i  = 0x5f3759df - ( i >> 1 );               // what the fuck?
	y  = * ( float * ) &i;
	y  = y * ( threehalfs - ( x2 * y * y ) );   // 1st iteration
//	y  = y * ( threehalfs - ( x2 * y * y ) );   // 2nd iteration, this can be removed

	return y;
}

肝は2行です。i = *(long*)&y は float のビット列を数値変換せず生の32ビット整数として読み替えます。次の 0x5f3759df - (i >> 1) が魔法で、鍵は IEEE754 の内部表現が対数の近似になっている点です。正の float は 符号(1) | 指数E(8) | 仮数M(23) と並び、値は概ね (1 + m) * 2^(E-127) です。このビット列 I を実数と見ると log2(値) はおおよそ (I / 2^23) - 127 に比例し、整数として読んだビット列はその数の2を底とする対数にほぼ線形対応 します。逆平方根の対数は log2(1/sqrt(x)) = -0.5 * log2(x) なので、対数の世界では「半分にして符号反転」で答えになります。i >> 1 が対数を半分にし、定数減算が符号反転と対数近似のずれ（オフセット）補正をまとめて担い、その最適オフセットをエンコードした値が 0x5f3759df です。それを y = *(float*)&i で float に読み戻します。

残る1行 y = y * (threehalfs - x2*y*y) はニュートン法の1ステップです。f(y) = 1/y^2 - x の零点を探すと反復式は y_next = y * (1.5 - 0.5*x*y*y) となり、コードと一致します。初期値の相対誤差は最大3%強ですが、2次収束するこの反復を1回通すと約0.175%へ一気に縮みます。コメントアウトされた2行目を活かせば誤差はさらに桁で下がりますが、ゲームには1回で十分と判断されました。

逸話と経緯

長らく作者は id の John Carmack だと噂されましたが本人ではありません。2005年のソース公開でも由来は明かされず、Beyond3D の Rys Sommefeldt が数年かけて出所をたどりました。判明した系譜はおおむね次のとおりです。

決定打は2006年です。Slashdot で話題化した調査を見た Greg Walsh 本人が Beyond3D に連絡し、自分がこの定数とアルゴリズムを考案したと認めました。あの2つのコメントを書いたのは Walsh ではなく id 側の誰か（Terje Mathisen や Michael Abrash の名が挙がる）とされますが確証はありません。要は「Carmackの魔法」という俗説は誤りで、1980年代のワークステーション文化で磨かれた技法が巡り巡ってゲームエンジンに載っていた、というのが史実です。

遺産と教訓

皮肉にも、有名になった2005年には実務的な役目はほぼ終わっていました。Quake III と同じ1999年、Intel は SSE に逆平方根命令 rsqrtss を追加します。ハードウェアが直接近似を返すため、ある Core 2 の計測では rsqrtss が約0.85ns 対 高速逆平方根の約3.54ns と速く、しかも誤差も小さいという結果でした。現代のx86やArmには同等命令があり、新規に Q_rsqrt を選ぶ理由はまずありません。関連する原理はグラフィックスやプログラミングも参照してください。