平方根の近似値 - ほっしーの技術ネタ備忘録

とある教授と話をしていて「なるほど！」と思ったのでメモ。

ベクトルの正規化などで平方根を求めたいけど
平方根は回路的にコストが高い。そんなときに使うウラワザ。

浮動小数は仮数と指数に分けて
$a\times2^k$
という形で記録されているけれど、ここでaにあたる仮数部は
二進数表記では1.000〜1.111…の間で表すことになっている。
(これをビットシフトすれば任意の実数が表せるため)

二進数表記での1.000〜1.111…といえば10進数に換算すると1.0〜1.999…であるため、
$2^{\frac{k}{2}}=\sqrt{2^k}\le\sqrt{a\times2^k}\lt\sqrt{2\times2^k}=\sqrt{2}\times2^{\frac{k}{2}}$
という不等式が成立する。

つまり、 $1.2\times2^{\frac{k}{2}}$ で近似すればおおよそ17%弱の誤差に収まる。
もっと大雑把に $2^{\frac{k}{2}}$ で近似しても誤差は41%程度だ。

17%を大きいと見るか小さいと見るかはケースバイケースだけれども計算量はぐっと減るし、
後者に至ってはシフト演算で済むので不可逆圧縮のような用途で有用らしい。
10進数で考えてる間は思いつかないことらしい。