2026年4月10日金曜日

🪄高速逆平方根（Fast Inverse Square Root）と“0x5f3759df”の正体：ニュートン法1回近似の仕組み

 高速逆平方根（Fast Inverse Square Root）は、Quake IIIで有名になったビットレベルの近似法です。0x5f3759dfというマジックナンバーで初期値を作り、ニュートン法1回で良好な精度を得ます。本稿ではその仕組みと、現代CPUのrsqrt命令との使い分けを簡潔に整理します。

このアルゴリズムは、もともとQuake III Arenaのソースコードで知られるようになりました。この方法は浮動小数点数のビット表現を利用しており、その際に使用される「マジックナンバー」は 0x5f3759df です。

以下がその典型的な実装例です（C言語風の擬似コード）：

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

x2 = number * 0.5F;
y  = number;
i  = *(long*)&y;                        // 浮動小数点数を整数として解釈
i  = 0x5f3759df - (i >> 1);             // マジックナンバーを使用
y  = *(float*)&i;                       // 整数を浮動小数点数に戻す
y  = y * (threehalfs - (x2 * y * y));   // ニュートン法の1回目の反復

return y;

}

このアルゴリズムは、ニュートン法を利用した反復処理によって逆平方根を非常に高速に近似することができます。 0x5f3759df は特定のハードウェアアーキテクチャに最適化されていたため、汎用的な用途では他の手法やライブラリを使用した方が良いこともありますが、この方法は歴史的に非常に有名です。

数理モデルやアルゴリズムにおいても、さまざまな「マジックナンバー」が使われており、特定の目的に最適化されたり、効率化を実現するために活用されています。以下に、いくつかの代表的な例を挙げます。

Bresenhamのアルゴリズム

グラフィックスにおける直線を描画する際に使われるBresenhamのアルゴリズムでは、整数の除算を避けるために「マジックナンバー」が使われることがあります。たとえば、ある特定のオフセットや初期値が結果を最適化するために手動で調整される場合があります。

ハッシュ関数のマジックナンバー

ハッシュ関数やチェックサムアルゴリズム（CRCなど）にもマジックナンバーが登場します。たとえば、MurmurHashやFNV-1aなどでは特定の「マジックプライム」が使用されており、これにより衝突率を低減し、結果の分散性が向上します。代表的なものとして以下があります：

MurmurHash3: 0x5bd1e995 という定数が使われる。

FNV-1a ハッシュ: FNV-1a では 0x811C9DC5 がオフセットベース、0x01000193 がプライム数として使われています。

Perlinノイズ

ノイズ生成のアルゴリズムであるPerlinノイズでも、補間やグラデーション計算で使用される5次の補間関数（6t^5 - 15t^4 + 10t^3）は、特定の補間品質を保つためにマジックナンバー的に構成されています。この形の補間関数は、滑らかなノイズ生成に適しているとされています。

Zigguratアルゴリズム

乱数生成アルゴリズムであるZigguratアルゴリズムでは、指数関数や正規分布からの乱数を効率的に生成するために、特定の閾値や定数（マジックナンバー）が使用されます。たとえば、テーブルを事前計算する際の値や、特定の「跳ね返り」範囲がマジックナンバーの形で事前に決定されています。

Sin/Cosの高速近似

三角関数の高速近似にもマジックナンバーが使われることがあります。特に古いゲームプログラミングでは、テーブルルックアップや特定の式を使ってsinやcosを近似する際に、特定の定数が使われます。

例えば、x * (π - x) / 2 などの式が三角関数の近似に使われることがあり、これもある意味でマジックナンバーを活用しています。

  1. メルセンヌ・ツイスタ

乱数生成アルゴリズムの代表例であるメルセンヌ・ツイスタでは、特定のパラメータである19937という数が周期長（2^19937−1）を決定する重要な定数として使用されています。また、初期化ベクトルや係数にもマジックナンバー的な定数が含まれています。

  1. Quakeの整数平方根

先ほどの高速逆平方根と同じく、整数の平方根を効率的に求めるためのアルゴリズムでは、特定のビットシフトやオフセットがマジックナンバーの形で使われることがあります。たとえば、2進法での最適化のためのビットマスクやシフト量が典型的です。

これらのマジックナンバーは、通常、実験や理論的な分析によって特定の問題に対して最適化されたものです。そのため、ある意味「謎めいている」ものが多く、効率的なアルゴリズムや計算において非常に重要な役割を果たしています。


投稿者