【効率のいい平方根の計算方法】

• 対象：初級プログラミング演習ⅠとかⅡ
• 前提：コンピュータは基本的には加算と減算は高速に可能。次に早いのが乗算で、一番遅いのは除算です。

さて、平方根の計算をプログラムで書くときに、[i x i=...]とやって、(i)をインクリメントしながら順番に計算する方法がまず思いつくのではないでしょうか。 とても非効率な気がします。では平方根を早く計算すればいいのか？が問題になります。

解決方法を考える細かい説明は置いておいて、私は平方根の逆数の近似値を計算する方法を選びました。 ※逆数は、ある数(a)を考えた時に、[a×b=1]になる(b)を(a)の逆数と言います（雑な説明）。 　平方根をニュートン法を用いて計算しようとすると除算が必要になり、平方根の逆数は除算が不要なのです。

平方根の逆数[1/√n]がとりあえず求まったら、(n)をかけて[√n]を求め、結果を別の変数(iとかcとか好きなの)ここでは仮に変数(c)に代入しておきます。 ※[1/√n]を有理化すると、[√n/n]になります。(n)を分数にすると[n/1]になります。[√n/n × n/1]を計算すると[n√n/n]になり約分すると[√n]になります。（中学校の算数）

先ほどの変数(c)は近似値ですが、[√n]よりは小さい値になっています。その為[c × c]を計算して(n)より小さければ(c)をインクリメントし、 [c+1 × c+1]を計算してみて(n)より小さければもう一度インクリメントし・・と繰り返し(n)ぴったりの数字が出てくればそれが答えになるはずです。 「√nを超えない最大の整数」を求めるのであれば、(n)を超えたらインクリメントする手前の(c)が(n)の平方根より小さい最大の整数となるはずです。

ということで肝心の計算方法ですが、先人が計算を行っているので習うとしましょう。

Quake-III-Arena/q_math.c at master · id-Software/Quake-III-Arena

これはとある昔のFPSのゲームのコードですが、GPL v2で公開されていますので適切に利用する分には問題ありません。 このURLのファイルで552行目から572行目までの関数Q_rsqrtが目的のものです。 566行目から570行目は不要なので削除して良いと思います。理由を忘れましたが私はfloatからdoubleで計算できるように改造しました。 (n)を引数として関数Q_rsqrtを呼ぶと[1/√n]が求まるので、あとは前者の通りの計算を行えば答えが出てくるはずです。

なるべく高校以上の数学を使わない説明を心掛けました。 もっと詳しいのは下記に列挙したURLをご覧いただければと思います。

A Brief History of InvSqrt - Matthew Robertson / Q_rsqrtの詳しい説明

Fast inverse square root - Wikipedia / History and investigationの項にfloatからdoubleに改造するヒントあり。

高速逆平方根計算アルゴリズムの小詳解 - at kaneshin / Go言語だけど、ほぼ同じコードで日本語での解説がある。