Babylonian Method

平方根の近似値を求めるアルゴリズムです．例えば，$\sqrt{5}$の推測値として最初にa=2とおいて，次の計算をします． $$\frac{1}{2}\left( a+\frac{5}{a} \right)$$ この計算で得た値を新たに$a$とおいて，同じ計算を繰り返します．
$$\begin{align} &\frac{1}{2}\left( 2+\frac{5}{2} \right)=\frac{9}{4}=2.25\\ &\frac{1}{2}\left( \frac{9}{4}+\frac{5}{\frac{9}{4}} \right)=\frac{161}{72}=2.236111111\cdot\cdot\cdot\\ &\frac{1}{2}\left( \frac{161}{72}+\frac{5}{\frac{161}{72}} \right)=\frac{51841}{23184}=2.236067978791\cdot\cdot\cdot\\ \end{align}$$ $\sqrt{5}=2.236067977499\cdot\cdot\cdot$なので，3回の計算で驚くほど速く$\sqrt{5}$に近づいたことが分かります．この方法はBabylonian MethodまたはHero's method（Heroはあのヘロンの公式のヘロンと同一人物）と呼ばれています．

この式をよく見ると，$a$と$\frac{5}{a}$のarithmetic mean（算術平均＝相加平均）を求める式になっています．面積が$s$になる長方形の1辺を$a$とすると，他の1辺は$\frac{s}{a}$になるので，これらの算術平均を新たな$a$として同じ計算を繰り返すと，正方形の1辺に近づいていくというわけです．

一般に$\sqrt{s}$を求める場合を漸化式で表せば次式になります． $$x_{n+1}=\frac{1}{2}\left( x_n+\frac{s}{x_n} \right)$$ 極限では$x_{n+1}$も$x_n$もほぼ同じなので，その値をαとおいて上式に代入すると， $$α=\frac{1}{2}\left( α+\frac{s}{α} \right)$$ 整理すれば，$α^2=s$すなわち，$α=\pm\sqrt{s}$となります．

これは17世紀頃に発見されたNewton's Method（ニュートン法） $$x_{n+1}=x_n-\frac{f(x_n)}{f'(x_n)}$$ に$f(x)=x^2-s$を当てはめた式と同じになりますが，もちろん，Babylonian Methodの方がずっと早くに知られていたことになります．

急速に近似する様子を確かめるものをGeoGebraでつくってみました．試してみてください．

因みに，平方根の近似値を求める方法は，小数点から 2 桁ずつ区切って割り算のようにする方法 extraction of square root（開平法）がよく知られています．

<Reference>
Methods of computing square roots
https://en.wikipedia.org/wiki/Methods_of_computing_square_roots