はじめに

JSのMath.sqrt関数が存在しない場合、自然数nの平方根はどうやって求められるか？

\sqrt{n}

バビロニア数学における平方根の近似計算方法をアルゴリズムとして利用すれば解けるらしい。

解いてみる

例えば、2の平方根を求めたい場合。

一旦1.5だとして見積もってみましょう。（実際には1.41421356と知りつつ）

\sqrt{1}<\sqrt{2}<\sqrt{4}\\
1<\sqrt{2}<2\\

2の平方根は、1と2の間であることはわかる。

同じ方法を小数点第一位まで求めてみる

1.0^2=1.00 \\
1.1^2=1.21 \\
1.2^2=1.44 \\
1.3^2=1.69 \\
1.4^2=1.96 \\
1.5^2=2.25 \\

2の平方根は 1.4 と 1.5 の間にあることがわかります。

どちらかといえば1.4の2乗に近いので、近似値を 1.4 とします。

同様に小数点第二位、三位と繰り返えせば近似値はどんどん性が高まりますが計算量が多くなりそうです。

そこで、バビロニア数学を使えば、計算量を抑えて近似値を求められます。やってみます。

自然数 2 の平方根の近似値を仮にxとすると

x^{2}≒2\\
x ≒ \frac{2}{x}

近似値は1.4なので

x ≒ \frac{2}{x}\\
1.4  ≒ \frac{2}{1.4}\\
1.4  ≒ 1.42857142857\\

バビロニア数学における平方根の近似計算方法は、

平方根の正しい値は、上記の２つの値の間にあるはずで、その平均値を推定値として何度か求めると、だんだん正確な値が推定できるという考え方です。

x と \frac{2}{x}　の平均

つまり

\frac{x+\frac{2}{x}}{2}

が近似値であると言えます。

この近似値の推定値を再帰的に計算し続ければ限りなく2の平方根はもとまるだろうというのがバビロニア数学の平方根の求め方です。ベースケースでは相対誤差0.1%のズレがなければ、それを回答として出力するようにします（プログラムでは）。

相対誤差 0.01% 未満なら、

x_{n}

を返す。

相対誤差 0.01% 以上なら、新たな推定値（Sは推定値）

\frac{x_{n-1}+\frac{S}{x_{n-1}}}{2}

JSで書くとこんな感じ

再帰的な処理を使って求めようとしています。

// 相対誤差：　誤差を理論値で割ったもの（理論値と測定値がどれほど離れているかを％で表す）
// ベースケース: 相対誤差が 0.01% 未満に収まるように設定
const isSquareRootCloseEnough = (a,b) => 100 * Math.abs((a-b)/b) < 0.01

const squareRootHelper = (x, guess) => {
    // バビロンの数学者は平方根の正しい値は guess と x/guess の平均（newGuess）である説
    let newGuess = (guess + x/guess)/2
    // ベースケース
    if(isSquareRootCloseEnough(newGuess, guess)) return guess
    // xが第一引数はintSquareRootのと変わらず。第二引数は newGuessで
    return squareRootHelper(x, newGuess)
}

// 平方根の近似値を返してくれる
const intSquareRoot = (x) => squareRootHelper(x, 1)

4回目まで手計算した結果も一致しているので間違いなさそう。

仮に、引数を12としたら...

intSquareRoot(12) で実行したら
return 28.63564310305401512
と返ってくる予定

手計算してみる。

あってそう。

結構シンプルなロジックなのに、平方根の近似値を計算できるなんて、すごいですね。

以上です。