この記事について
低レイヤや古いCPU環境では「重い演算をどう軽くするか」が常に課題でした。
ここではQuake III に実装されたことで有名な inverse square root を皮切りに、いくつかのトリックを整理します。
※あくまで技術的な観点での紹介であり、現在ではそれぞれ高速なCPU命令が実装されているため、直接利用することは、ほとんどないと思われることに注意してください。
トリック集
1. Fast Inverse Square Root（逆二乗根）
概要
$1/sqrt(x)$を高速に求めるための手法です。浮動小数点のビット列を符号なし整数として再解釈し、ビット操作で対数的な近似を作り、ニュートン法で精度を改善しています。
効果
- 特定のCPU/GPU環境でハードウェア演算より高速に逆二乗根を計算
疑似コード
float fast_rsqrt(float x) {
float x2 = x * 0.5f;
int i = *(int*)&x; // float を int として読む
i = 0x5f3759df - (i >> 1); // マジックナンバー
float y = *(float*)&i; // 変形したiの値を再びfloatとして読んで近似値を得る
y = y * (1.5f - x2 * y * y); // ニュートン法で補正(1回)
return y;
}
2. Fast Square Root（平方根）
概要
平方根 $sqrt(x)$ を近似する手法です。同様にfloatのビットパターンを整数に解釈して指数を半分にして、ニュートン法で補正しています。
効果
- 除算不要で平方根を計算
- ゲーム機や組み込み環境で利用
- ただし、実際は高速逆平方根の応用（x * rsqrt(x)）の方が利用されている
疑似コード
float fast_sqrt(float x) {
int i = *(int*)&x;
i = (i >> 1) + 0x1fc00000; // マジックナンバー
float y = *(float*)&i;
y = 0.5f * (y + x / y); // ニュートン法による補正
return y;
}
3. Fast Reciprocal（逆数）
概要
$1/x$の高速近似の手法です。同様にfloatのビットパターンから初期近似を作り、ニュートン法で補正しています。
効果
- 除算命令が重い環境で、逆数なしで逆数を計算
- グラフィックスや物理シミュレーションで利用
疑似コード
float fast_rcp(float x) {
int i = *(int*)&x;
i = 0x7EEEEBB3 - i; // マジックナンバー
float y = *(float*)&i;
y = y * (2.0f - x * y); // ニュートン法で補正（１回）
return y;
}
4. Fast Logarithm（対数）
概要
$log(x)$の近似です。すべてのテクニックにおいて、この考え方が使われています。
効果
- 一部のニューラルネットやDSPの高速化に利用
- exp の逆変換にも応用可能
- 低精度で十分な場面に限る
疑似コード
float fast_log2(float x) {
int i = *(int*)&x;
float y = (float)i;
return (y * (1.0f / (1 << 23))) - 127.0f; // 粗い近似式
}
5. Fast Exponential（指数）
概要
$exp(x)$を浮動小数点のビットから直接構築して近似した手法です。log の逆手法となっています。
効果
- シェーダや機械学習の高速化
- 低精度で十分なケース（エフェクトなど）に有効
- 低精度で十分な場面に限る
疑似コード
float fast_exp(float x) {
float y = x * 12102203.0f + 127.0f * (1 << 23); // x をlog2スケールに変換しfloatのビット列を構築
int i = (int)y;
return *(float*)&i; // exp(x) の近似値
}
補足
なぜ「float を整数として読む」と log₂ 近似になるのか？
先に概要
最終的に欲しいのは「$y = 1/\sqrt{x}$ の数値」です。ただし、この演算が負荷が高い場合において、別の低負荷の演算の組み合わせで近似したい動機があります。
- 値 $y$ があれば、その IEEE754 floatのビット表現から整数 $I_y$ を作れます
- 逆に「整数 $I_y$ を float と解釈」すれば、その値 $y$ が得られます
- この関係は$$I_y = 2^{23}(127 + \log_2(y))$$ となります
逆二乗根の近似をするときに、いきなり負荷が高い $y$ を演算するのではなく
- 「欲しい $\log_2(y)$」を整数近似で作る
- そこから「対応するビット列 $I_y$」を作って、floatに戻す
という流れを取ります。この処理が軽くなるには、$\log_2(y)$の整数近似が簡単である必要があります。幸いにも、この処理を近似する手法があり、今回のテクニックに使われています。
float と log_2(x) の関係
IEEE 754 単精度浮動小数点は以下の形で表されます。※( )内の数値はビット数。
[ 符号sign (1) ][ 指数部E (8) ][ 仮数部M (23) ]
数値としては以下の計算式で表されます。
$$
x = (-1)^{sign} \times 2^{E-127} \times \left(1 + \frac{M}{2^{23}}\right)
$$
ここで $E$ は指数部、$M$ は仮数部、127 はfloatのバイアスです。
この式の両辺に対してlog₂ を取ると下記が得られます。
$$
\log_2(x) = (E - 127) + \log_2\left(1+\frac{M}{2^{23}}\right)
$$
ここで $(E-127)$ は「$\log_2$ の整数部」、$M/2^{23}$ は「$\log_2$ 小数部の補正」に対応しています。
一方で、float をそのまま int として解釈すると、そのビット列$I$の値は下記となります。
$$
I = 2^{23} \cdot (E + M/2^{23})
$$
ここで両辺を $2^{23}$ で割り、さらに両辺に-127をつけてみます。
$$
\frac{I}{2^{23}} -127 = (E - 127) + \frac{M}{2^{23}}
$$
この$\frac{I}{2^{23}}-127$ の右辺と $\log_2(x)$ を見比べると、「整数部は同じ$(E-127)$で、小数部だけを $M/2^{23}$ で置き換えた近似」になっていることがわかります。
そのため、下記のように大胆に近似することができると考えられます。
$$
\log_2(x) \approx\left(\frac{I}{2^{23}} - 127\right)
$$
logの値が手に入ったため、ここからfloatに戻すことができます。
$1/\sqrt{x}$の場合は、下記となります。$I$は$x$のfloat表現です。
$$
\log_2(x^{1/2}) = -\frac{1}{2}\left(\frac{I}{2^{23}} - 127\right)
$$
$逆数の場合は、下記となります。
$$
\log_2(x^{-1}) = -\left(\frac{I}{2^{23}} - 127\right)
$$
マジックナンバーの演算 (高速逆平方根のケース）
ビット表現は下記となります。
$$
I_y = 2^{23}(127 + \log_2(x^{1/2})) = 2^{23}\left(127 -\frac{1}{2}\left(\frac{I}{2^{23}} - 127 \right) \right)
$$
$$
= 2^{23}\cdot 127 - \tfrac{I}{2} + 2^{23}\cdot \tfrac{127}{2}
$$
$$
= 2^{23}\Bigl(127+\tfrac{127}{2}\Bigr) - \tfrac{I}{2}
$$
すなわち下記のような形となります。
$$
I_y \approx\ A_0 - (I \gg 1),
\qquad
A_0 = 2^{23}\cdot 190.5 \approx 0x5f400000
$$
これで 「マジックナンバー定数 − (I >> 1)」 という 整数演算の形に到達します。
トリックの整理
改めて整理します。この性質を応用することで
- 整数ビット列を簡単な定数演算で変形する → log の近似計算が一瞬でできる
- 「平方根」「逆数」「指数」「対数」など log に関係する関数の初期近似が作れる
- 仕上げにニュートン法で補正すれば十分な精度になる
という流れになります。
つまり、「浮動小数点 = log 構造を持つ表現形式」 であることを利用しているのが、これらトリックの核心アイデアです。