平方根を計算する方法

平方根を計算する方法は、正の実数の非負の平方根を近似するアルゴリズムです。完全平方以外の自然数の平方根はすべて無理数であるため、^[1] 平方根は通常、有限の精度でしか計算できません。これらの方法では通常、精度が徐々に高くなる一連の近似値を構築します。 ${\displaystyle {\sqrt {S}}}$ ${\displaystyle S}$

ほとんどの平方根の計算方法は反復的です。 の適切な初期推定値を選択した後、何らかの終了基準が満たされるまで反復的な改良が実行されます。 改良スキームの 1 つに、ニュートン法の特殊なケースであるヘロン法があります。 除算が乗算よりもはるかにコストがかかる場合は、代わりに逆平方根を計算する方が望ましい場合があります。 ${\displaystyle {\sqrt {S}}}$

平方根を桁ごとに計算する方法や、テイラー級数を使用する方法もあります。平方根の有理近似値は、連分数展開を使用して計算できます。

採用される方法は、必要な精度、利用可能なツール、計算能力によって異なります。方法は、暗算に適したもの、通常は少なくとも紙と鉛筆を必要とするもの、デジタル電子コンピュータまたはその他の計算デバイスで実行されるプログラムとして実装されるものに大まかに分類できます。アルゴリズムでは、収束 (指定された精度を達成するために必要な反復回数)、個々の操作 (除算など) または反復の計算の複雑さ、およびエラーの伝播 (最終結果の精度) が考慮される場合があります。

紙と鉛筆による合成除算や級数展開などのいくつかの方法では、開始値は必要ありません。一部のアプリケーションでは、最も近い整数に丸められた、または切り捨てられた平方根である整数平方根が必要です (この場合は、修正された手順が使用される場合があります)。

平方根（特に2 の平方根）を求める手順は、少なくとも紀元前 17 世紀の古代バビロニアの時代から知られていました。 バビロニアの数学者は2 の平方根を 1 の後の 60 進法の 3 桁で計算しましたが、その正確な方法はわかっていません。彼らは斜辺を （たとえば、高さがロッド、幅がロッドの門の対角線）を使って近似する方法を知っており、同様のアプローチを使用して^[2]の近似値を求めていた可能性があります。$${\displaystyle {\sqrt {a^{2}+b^{2}}}\approx a+{\frac {1}{2}}b^{2}a^{-1}}$$${\displaystyle {\frac {41}{60}}+{\frac {15}{3600}}}$${\displaystyle {\frac {40}{60}}}$${\displaystyle {\frac {10}{60}}}$${\displaystyle {\sqrt {2}}.}$

1世紀エジプトのヘロン法は、平方根を計算するための最初の確認可能なアルゴリズムでした。^[3]

現代の分析手法は、ルネサンス初期に西ヨーロッパにアラビア数字が導入されてから開発され始めました。 ^[要出典]

現在、ほぼすべてのコンピューティング デバイスには、プログラミング言語構造、コンパイラの組み込み関数またはライブラリ関数、または説明した手順のいずれかに基づくハードウェア演算子として、高速で正確な平方根関数が備わっています。

多くの反復平方根アルゴリズムでは、初期シード値が必要です。シードは 0 以外の正の数で、平方根を求める必要がある数である 1 から までの範囲でなければなりません。これは、平方根がその範囲内になければならないためです。シードが平方根から大きく離れている場合、アルゴリズムはより多くの反復を必要とします。(または) で初期化すると、平方根の大きさの桁を取得するだけで、おおよそ 回の反復が無駄になります。したがって、精度は限られるかもしれませんが計算しやすい大まかな推定値があると便利です。一般に、初期推定値が優れているほど、収束は速くなります。ニュートン法 (バビロニア法またはヘロン法とも呼ばれる) では、平方根よりいくらか大きいシードは、平方根よりいくらか小さいシードよりもわずかに速く収束します。 ${\displaystyle S}$${\displaystyle x_{0}=1}$${\displaystyle S}$${\displaystyle {\tfrac {1}{2}}\vert \log _{2}S\vert }$

一般に、推定は根を含むことが分かっている任意の区間（ など）に従います。推定は、区間における への関数近似の特定の値です。より良い推定を得るには、区間のより厳しい境界を得るか、 へのより良い関数近似を見つける必要があります。後者は通常、近似に高次の多項式を使用することを意味しますが、すべての近似が多項式であるとは限りません。一般的な推定方法には、スカラー、線形、双曲、対数などがあります。暗算または紙と鉛筆による推定には、通常、10 進法が使用されます。コンピュータによる推定には、2 進法がより適しています。推定では、数値が科学的記数法で表されるため、指数と仮数は通常別々に扱われます。 ${\displaystyle [x_{0},S/x_{0}]}$${\displaystyle f(x)={\sqrt {x}}}$${\displaystyle f(x)}$

通常、この数値は科学的記数法でと表されます。ここで、n は整数であり、平方根の可能な範囲はです。 ${\displaystyle S}$${\displaystyle a\times 10^{2n}}$${\displaystyle 1\leq a<100}$${\displaystyle {\sqrt {a}}\times 10^{n}}$${\displaystyle 1\leq {\sqrt {a}}<10}$

スカラー法では、範囲を区間に分割し、各区間の推定値は単一のスカラー数で表されます。範囲を単一の区間とみなす場合、算術平均 (5.5) または幾何平均 ( ) の時間が妥当な推定値となります。これらの絶対誤差と相対誤差は異なります。一般に、単一のスカラーは非常に不正確です。範囲を 2 つ以上の区間に分割すると推定値が向上しますが、スカラー推定値は本質的に精度が低くなります。 ${\displaystyle {\sqrt {10}}\approx 3.16}$${\displaystyle 10^{n}}$

2つの区間を幾何的に分割した場合、平方根は次のように推定できる^[注1]。${\displaystyle {\sqrt {S}}={\sqrt {a}}\times 10^{n}}$ $${\displaystyle {\sqrt {S}}\approx {\begin{cases}2\cdot 10^{n}&{\text{if }}a<10,\\6\cdot 10^{n}&{\text{if }}a\geq 10.\end{cases}}}$$

この推定値は、a = 100 で最大絶対誤差となり、a = 1 で最大相対誤差が 100% となります。 ${\displaystyle 4\cdot 10^{n}}$

たとえば、を として因数分解すると、推定値は となり、絶対誤差は 246、相対誤差はほぼ 70% になります。 ${\displaystyle S=125348}$${\displaystyle 12.5348\times 10^{4}}$${\displaystyle {\sqrt {S}}\approx 6\cdot 10^{2}=600}$${\displaystyle {\sqrt {125348}}=354.0}$

よりよい推定値、そして使用される標準的な方法は、小さな円弧上の関数の線形近似です。上記のように、底の累乗が数から因数分解され、区間が に縮小された場合、円弧にまたがる割線、または円弧に沿ったどこかの接線が近似値として使用されますが、円弧と交差する最小二乗回帰線の方がより正確です。 ${\displaystyle y=x^{2}}$${\displaystyle S}$${\displaystyle [1,100]}$

最小二乗回帰直線は、推定値と関数の値の平均差を最小化します。その方程式は です。並べ替え、計算を容易にするために係数を丸めます。 ${\displaystyle y=8.7x-10}$${\displaystyle x=0.115y+1.15}$$${\displaystyle {\sqrt {S}}\approx (a/10+1.2)\cdot 10^{n}}$$

これは、区間 における関数 y=x ²の単一部分線形近似によって達成できる平均的に最良の推定値です。a=100 で最大絶対誤差は 1.2、S=1 および 10 で最大相対誤差は 30% です。^{[注 2]}${\displaystyle [1,100]}$

10 で割るには、 の指数から 1 を引くか、比喩的に小数点を 1 桁左に移動します。この定式化では、任意の加法定数 1 に小さな増分を加えたものが適切な推定値となるため、正確な数値を覚えておくことは負担にはなりません。範囲を 1 本の線で結んだ近似値 (四捨五入の有無にかかわらず) は、精度の有効桁数が 1 未満です。相対誤差は 1/2 ²より大きいため、提供される情報は 2 ビット未満です。範囲が 2 桁と、この種の推定値としては非常に大きいため、精度は大幅に制限されます。 ${\displaystyle a}$${\displaystyle [1,100]}$

区分線形近似、つまり複数の線分でそれぞれ元の円弧の一部を近似すると、より正確な推定値が得られます。使用する線分が多いほど、近似値は高くなります。最も一般的な方法は接線を使用することです。重要な選択は、円弧をどのように分割するか、どこに接点を配置するかです。円弧をy  = 1からy  = 100 まで分割する効果的な方法は、幾何学的に分割することです。2 つの区間の場合、区間の境界は元の区間の境界の平方根 1×100、つまり [1, ² √ 100 ] と [ ² √ 100 ,100] になります。 3 つの区間の場合、境界は 100 の 3 乗根です: [1, ³ √ 100 ]、[ ³ √ 100 ,( ³ √ 100 ) ² ]、[( ³ √ 100 ) ² ,100] など。2 つの区間の場合、² √ 100 = 10 となり、非常に便利な数となります。接線は簡単に導出でき、x = √ 1* √ 10およびx = √ 10* √ 10にあります。それらの式は、 およびです。これを反転すると、平方根は、およびです。したがって、 の場合: ${\displaystyle y=3.56x-3.16}$${\displaystyle y=11.2x-31.6}$${\displaystyle x=0.28y+0.89}$${\displaystyle x=.089y+2.8}$${\displaystyle S=a\cdot 10^{2n}}$$${\displaystyle {\sqrt {S}}\approx {\begin{cases}(0.28a+0.89)\cdot 10^{n}&{\text{if }}a<10,\\(.089a+2.8)\cdot 10^{n}&{\text{if }}a\geq 10.\end{cases}}}$$

絶対誤差の最大値は、区間の最高点であるa =10 と 100 で発生し、それぞれ 0.54 と 1.7 です。相対誤差の最大値は、区間の終点であるa =1、10、100 で発生し、どちらの場合も 17% です。17% または 0.17 は 1/10 より大きいため、この方法では小数点以下の精度しか得られません。

場合によっては、双曲線推定が有効なことがあります。双曲線も凸曲線であり、直線よりもY = x ²の弧に沿っている可能性が高いためです。双曲線推定は、浮動小数点除算を必要とするため、計算がより複雑になります。区間上のx ²のほぼ最適な双曲線近似は、y=190/(10-x)-20 です。転置すると、平方根は x = -190/(y+20)+10 です。したがって、 ${\displaystyle [1,100]}$${\displaystyle S=a\cdot 10^{2n}}$$${\displaystyle {\sqrt {S}}\approx \left({\frac {-190}{a+20}}+10\right)\cdot 10^{n}}$$

浮動小数点除算は、小数点 1 桁まで正確であれば十分です。これは、全体的な推定値がその精度で、頭の中で実行できるためです。双曲推定値は、平均するとスカラー推定値や線形推定値よりも優れています。最大絶対誤差は 100 で 1.58、最大相対誤差は 10 で 16.0% です。a=10 での最悪のケースでは、推定値は 3.67 です。10 から始めてすぐにニュートン ラプソン反復法を適用すると、双曲推定値の精度を超えるまでに 2 回の反復が必要になり、3.66 になります。75 のようなより一般的なケースでは、双曲推定値は 8.00 で、より正確な結果を得るには 75 から 5 回のニュートン ラプソン反復法が必要になります。

区分線形近似に似ていますが、代数方程式の代わりに算術のみを使用する方法では、掛け算表を逆に使用します。1 から 100 までの数の平方根は 1 から 10 の間です。したがって、25 が完全な平方数 (5 × 5) で、36 が完全な平方数 (6 × 6) であることがわかっている場合、25 以上 36 未満の数の平方根は 5 で始まります。他の平方数の間の数についても同様です。この方法では最初の桁は正しくなりますが、1 桁正確ではありません。たとえば、35 の平方根の最初の桁は 5 ですが、35 の平方根はほぼ 6 です。

より良い方法は、範囲を正方形の中間で間隔に分割することです。したがって、25 から 36 の中間 (30.5) までの数値は 5 と推定し、30.5 より大きく 36 までの数値は 6 と推定します。^{[注 3]} この手順では、掛け算表から 2 つの積の中間の境界数を見つけるために少しの計算を行うだけです。次に、境界の参照表を示します。

最後の演算は推定値kに10の累乗を2で割った値を掛けることです。つまり、 ${\displaystyle S=a\cdot 10^{2n}}$$${\displaystyle {\sqrt {S}}\approx k\cdot 10^{n}}$$

この方法では、最適な最初の桁に丸められるため、暗黙的に 1 桁の精度が得られます。

この方法は、ほとんどの場合、被演算子を囲む最も近い正方形の間を補間することで、3桁の有効数字まで拡張できます。 の場合、 はほぼkプラス分数であり、 aとk ²の差を2つの正方形の差で割ったものです。 ここで${\displaystyle k^{2}\leq a<(k+1)^{2}}$${\displaystyle {\sqrt {a}}}$$${\displaystyle {\sqrt {a}}\approx k+R}$$$${\displaystyle R={\frac {(a-k^{2})}{(k+1)^{2}-k^{2}}}}$$

最終的な演算は、上記のように、結果に 10 の累乗を 2 で割った値を掛けることです。 $${\displaystyle {\sqrt {S}}={\sqrt {a}}\cdot 10^{n}\approx (k+R)\cdot 10^{n}}$$

kは 10 進数で、R は10 進数に変換する必要がある分数です。通常、分子には 1 桁、分母には 1 桁または 2 桁しかないため、10 進数への変換は頭の中で行うことができます。

例: 75 の平方根を求めます。75 = 75 × 10 ^{2  · 0}なので、aは 75、nは 0 です。九九から、仮数の平方根は8 × 8 は 64 ですが、 9 × 9 は 81 で大きすぎるため、 8 の小数点数でなければなりません。kは8 です。はRの 10 進数表現です。分数Rは、分子が 75 - k ² = 11、分母が 81 - k ² = 17 です。11/17 は 12/18 より少し小さいので、これは 2/3 または .67 なので、 .66 と推測します (ここでは推測しても問題ありません。誤差は非常に小さいです)。したがって、推定値は8 + .66 = 8.66です。√ 75 を3 桁有効数字にすると 8.66 となるため、推定値は 3 桁有効数字まで正確です。この方法を使用した推定値はすべて正確であるとは限りませんが、近い値になります。

2進数体系で作業する場合（コンピュータ内部で行われるように）、 と表すと、平方根は次のように推定できる。 ${\displaystyle S}$${\displaystyle a\times 2^{2n}}$${\displaystyle 0.1_{2}\leq a<10_{2}}$${\displaystyle {\sqrt {S}}={\sqrt {a}}\times 2^{n}}$$${\displaystyle {\sqrt {S}}\approx (0.485+0.485\cdot a)\cdot 2^{n}}$$

これは、3 つの重要な数字の係数に対する最小二乗回帰直線です。 =2での最大絶対誤差は 0.0408 、=1 での最大相対誤差は 3.0% です。計算上便利な丸め推定値 (係数が 2 の累乗であるため) は次のようになります。 ${\displaystyle {\sqrt {a}}}$${\displaystyle a}$${\displaystyle a}$

${\displaystyle {\sqrt {S}}\approx (0.5+0.5\cdot a)\cdot 2^{n}}$^[注4]

最大絶対誤差は2で0.086、最大相対誤差はa = 0.5およびa = 2.0で6.1%です。

の場合、バイナリ近似は になります。なので、推定値の絶対誤差は 19、相対誤差は 5.3% になります。 相対誤差は 1/2 ⁴より少し小さいので、推定値は 4 ビット以上まで良好です。 ${\displaystyle S=125348=1\;1110\;1001\;1010\;0100_{2}=1.1110\;1001\;1010\;0100_{2}\times 2^{16}\,}$${\displaystyle {\sqrt {S}}\approx (0.5+0.5\cdot a)\cdot 2^{8}=1.0111\;0100\;1101\;0010_{2}\cdot 1\;0000\;0000_{2}=1.456\cdot 256=372.8}$${\displaystyle {\sqrt {125348}}=354.0}$

の上位 8 ビットをテーブル検索することで、8 ビットまでの良好な値の推定値を取得できます。ただし、ほとんどの浮動小数点表現では上位ビットは暗黙的であり、8 の下位ビットは丸められる必要があることに注意してください。テーブルは、計算済みの 8 ビット平方根値の 256 バイトです。たとえば、 1.8515625 ₁₀を表すインデックス 11101101 ₂の場合、エントリは 10101110 _{2で、これは 1.8515625 10}の平方根を 8 ビット精度 (2 桁以上の 10 進数) で表した 1.359375 ₁₀を表します。 ${\displaystyle a}$${\displaystyle a}$

近似値を求める最初の明示的なアルゴリズムは、1世紀のギリシャの数学者アレクサンドリアのヘロンが西暦60年の著書『計量学』でその方法を説明したことにちなんで、ヘロン法と呼ばれています。^{[3]この方法は}バビロニア法とも呼ばれますが（斜辺を近似するバビロニア法と混同しないように注意）、バビロニア人がこの方法を知っていたという証拠はありません。 ${\displaystyle \ {\sqrt {S~}}\ }$

正の実数 が与えられたとき、x ₀ > 0 を任意の正の初期推定値とする。ヘロン法は、 所望の精度が達成されるまで繰り返し計算を行う。この式で定義される数列は次のように収束する。${\displaystyle S}$$${\displaystyle x_{n+1}={\frac {1}{2}}\left(x_{n}+{\frac {S}{x_{n}}}\right),}$$${\displaystyle \ {\bigl (}\ x_{0},\ x_{1},\ x_{2},\ x_{3},\ \ldots \ {\bigr )}\ }$${\displaystyle \ \lim _{n\to \infty }x_{n}={\sqrt {S~}}~.}$

これは、ニュートン法を使用してを解くことと同じです。このアルゴリズムは2 次収束します。つまり、 の正しい桁の数は、各反復ごとにほぼ 2 倍になります。 ${\displaystyle x^{2}-S=0}$${\displaystyle x_{n}}$

基本的な考え方は、が非負の実数の平方根に対して過大評価されている場合はが過小評価され、その逆も同様であるため、これら 2 つの数値の平均はより適切な近似値を提供すると合理的に期待できるというものです (ただし、この主張の正式な証明は算術平均と幾何平均の不等式に依存しており、平方根に関する記事で述べたように、この平均は常に平方根に対して過大評価されるため、収束が保証されます)。 ${\displaystyle \ x\ }$${\displaystyle \ S\ }$${\displaystyle \ {\tfrac {\ S\ }{x}}\ }$

より正確には、が の初期推定値であり、が推定値の誤差である場合、二項式を次のように展開することができます。 そして誤差項を解くと、 ${\displaystyle \ x\ }$${\displaystyle \ {\sqrt {S~}}\ }$${\displaystyle \ \varepsilon \ }$${\displaystyle \ S=\left(x+\varepsilon \right)^{2}\ ,}$$${\displaystyle \ {\bigl (}\ x+\varepsilon \ {\bigr )}^{2}=x^{2}+2x\varepsilon +\varepsilon ^{2}}$$

${\displaystyle \varepsilon ={\frac {\ S-x^{2}\ }{\ 2x+\varepsilon \ }}\approx {\frac {\ S-x^{2}\ }{2x}}\ ,}$もしそうであれば${\displaystyle \ \varepsilon \ll x~}$

したがって、誤差を補正し、古い推定値を次のように更新することができます 。計算された誤差は正確ではなかったため、これは実際の答えではありませんが、次の修正ラウンドで使用する新しい推定値になります。更新プロセスは、必要な精度が得られるまで繰り返されます。 $${\displaystyle \ x+\varepsilon \ \approx \ x+{\frac {\ S-x^{2}\ }{2x}}\ =\ {\frac {\ S+x^{2}\ }{2x}}\ =\ {\frac {\ {\frac {S}{\ x\ }}+x\ }{2}}\ \equiv \ x_{\mathsf {revised}}~.}$$

このアルゴリズムはp進数でも同様に機能しますが、実数の平方根をp進数の平方根と同一視するためには使用できません。たとえば、この方法を使用すると、実数では+3に収束しますが、 2 進数では -3に収束する有理数列を作成できます。

を6桁の有効数字で計算するには、上記の概算方法を使用して ${\displaystyle \ {\sqrt {S~}}\ }$${\displaystyle \ S=125348\ ,}$$${\displaystyle {\begin{aligned}{\begin{array}{rlll}x_{0}&=6\cdot 10^{2}&&=600.000\\[0.3em]x_{1}&={\frac {\ 1\ }{2}}\left(x_{0}+{\frac {S}{\;x_{0}\ }}\right)&={\frac {\ 1\ }{2}}\left(600.000+{\frac {\ 125348\ }{600.000}}\right)&=404.457\\[0.3em]x_{2}&={\frac {\ 1\ }{2}}\left(x_{1}+{\frac {S}{\;x_{1}\ }}\right)&={\frac {\ 1\ }{2}}\left(404.457+{\frac {\ 125348\ }{404.457}}\right)&=357.187\\[0.3em]x_{3}&={\frac {\ 1\ }{2}}\left(x_{2}+{\frac {S}{\;x_{2}\ }}\right)&={\frac {\ 1\ }{2}}\left(357.187+{\frac {\ 125348\ }{357.187}}\right)&=354.059\\[0.3em]x_{4}&={\frac {\ 1\ }{2}}\left(x_{3}+{\frac {S}{\;x_{3}\ }}\right)&={\frac {\ 1\ }{2}}\left(354.059+{\frac {\ 125348\ }{354.059}}\right)&=354.045\\[0.3em]x_{5}&={\frac {\ 1\ }{2}}\left(x_{4}+{\frac {S}{\;x_{4}\ }}\right)&={\frac {\ 1\ }{2}}\left(354.045+{\frac {\ 125348\ }{354.045}}\right)&=354.045\ \end{array}}\end{aligned}}}$$

したがって小数点以下3桁までです。 ${\displaystyle \ {\sqrt {125348~}}\approx 354.045\ }$

と仮定すると、任意の自然数に対して、相対誤差が次のように定義され 、 ${\displaystyle \ x_{0}>0~~{\mathsf {and}}~~S>0~.}$${\displaystyle \ n:x_{n}>0~.}$${\displaystyle \ x_{n}\ }$$${\displaystyle \ \varepsilon _{n}={\frac {~x_{n}\ }{\ {\sqrt {S~}}\ }}-1>-1\ }$$$${\displaystyle \ x_{n}={\sqrt {S~}}\cdot \left(1+\varepsilon _{n}\right)~.}$$

すると、 $${\displaystyle \ \varepsilon _{n+1}={\frac {\varepsilon _{n}^{2}}{2(1+\varepsilon _{n})}}\geq 0~.}$$

したがって 、収束が保証され、二次方程式となります。 $${\displaystyle \ \varepsilon _{n+2}\leq \min \left\{\ {\frac {\ \varepsilon _{n+1}^{2}\ }{2}},{\frac {\ \varepsilon _{n+1}\ }{2}}\ \right\}\ }$$

上記の大まかな推定をバビロニア方式で使用する場合、最も精度の低いケースは昇順で次のようになります。 $${\displaystyle {\begin{aligned}S&=\ 1\ ;&x_{0}&=\ 2\ ;&x_{1}&=\ 1.250\ ;&\varepsilon _{1}&=\ 0.250~.\\S&=\ 10\ ;&x_{0}&=\ 2\ ;&x_{1}&=\ 3.500\ ;&\varepsilon _{1}&<\ 0.107~.\\S&=\ 10\ ;&x_{0}&=\ 6\ ;&x_{1}&=\ 3.833\ ;&\varepsilon _{1}&<\ 0.213~.\\S&=\ 100\ ;&x_{0}&=\ 6\ ;&x_{1}&=\ 11.333\ ;&\varepsilon _{1}&<\ 0.134~.\end{aligned}}}$$

いずれにせよ、 $${\displaystyle {\begin{aligned}\varepsilon _{1}&\leq 2^{-2}.\\\varepsilon _{2}&<2^{-5}<10^{-1}~.\\\varepsilon _{3}&<2^{-11}<10^{-3}~.\\\varepsilon _{4}&<2^{-23}<10^{-6}~.\\\varepsilon _{5}&<2^{-47}<10^{-14}~.\\\varepsilon _{6}&<2^{-95}<10^{-28}~.\\\varepsilon _{7}&<2^{-191}<10^{-57}~.\\\varepsilon _{8}&<2^{-383}<10^{-115}~.\end{aligned}}}$$

丸め誤差により収束が遅くなります。重大な丸め誤差を回避するために、計算対象 の必要な精度よりも少なくとも 1 桁多く残しておくことをお勧めします。${\displaystyle \ x_{n}\ }$

平方根の近似値を求めるこの方法は、バクシャーリ写本と呼ばれる古代インドの写本に記載されています。これは、 x ₀から始まるバビロニア法の2回の反復に相当します。したがって、このアルゴリズムは4次収束します。つまり、近似値の正しい桁の数は、反復ごとにほぼ4倍になります。^[4]現代の表記法を使用した元の表現は次のとおりです。 を計算するには、を の初期近似値とします。次に、次のように繰り返します。 ${\displaystyle {\sqrt {S}}}$${\displaystyle x_{0}^{2}}$${\displaystyle S}$$${\displaystyle {\begin{aligned}a_{n}&={\frac {S-x_{n}^{2}}{2x_{n}}},\\b_{n}&=x_{n}+a_{n},\\x_{n+1}&=b_{n}-{\frac {a_{n}^{2}}{2b_{n}}}=(x_{n}+a_{n})-{\frac {a_{n}^{2}}{2(x_{n}+a_{n})}}.\end{aligned}}}$$

これを使って、整数から始めて平方根の有理近似値を構築することができます。がに近い整数で、 が絶対値が最小となる差である場合、最初の反復は次のように記述できます。 ${\displaystyle x_{0}=N}$${\displaystyle N^{2}}$${\displaystyle S}$${\displaystyle d=S-N^{2}}$$${\displaystyle {\sqrt {S}}\approx N+{\frac {d}{2N}}-{\frac {d^{2}}{8N^{3}+4Nd}}={\frac {8N^{4}+8N^{2}d+d^{2}}{8N^{3}+4Nd}}={\frac {N^{4}+6N^{2}S+S^{2}}{4N^{3}+4NS}}={\frac {N^{2}(N^{2}+6S)+S^{2}}{4N(N^{2}+S)}}.}$$

バクシャリ法は分数根を含む任意の根の計算に一般化できる。^[5]

バビロニア法と同じ例を使って、最初の反復では次のようになる。 ${\displaystyle S=125348.}$$${\displaystyle {\begin{aligned}x_{0}&=600\\[1ex]a_{0}&={\frac {125348-600^{2}}{2\times 600}}&&=&-195.543\\[1ex]b_{0}&=600+(-195.543)&&=&404.456\\[1ex]x_{1}&=404.456-{\frac {(-195.543)^{2}}{2\times 404.456}}&&=&357.186\end{aligned}}}$$

同様に2回目の反復では $${\displaystyle {\begin{aligned}a_{1}&={\frac {125348-357.186^{2}}{2\times 357.186}}&&=&-3.126\\[1ex]b_{1}&=357.186+(-3.126)&&=&354.060\\[1ex]x_{2}&=354.06-{\frac {(-3.1269)^{2}}{2\times 354.06}}&&=&354.046\end{aligned}}}$$

これは、数列内の平方根の各桁を求める方法です。この方法は二項定理に基づいており、基本的には逆アルゴリズムで解くものです。バビロニア法よりも遅いですが、いくつかの利点があります。 ${\displaystyle (x+y)^{2}=x^{2}+2xy+y^{2}}$

• 手動で計算する方が簡単になります。
• 見つかったルートのすべての数字は正しいことが分かっています。つまり、後で変更する必要はありません。
• 平方根の展開が終了している場合、アルゴリズムは最後の桁が見つかった時点で終了します。したがって、これは与えられた整数が平方数であるかどうかを確認するために使用できます。
• このアルゴリズムはどの基数でも機能しますが、当然ながら、その進行方法は選択された基数によって異なります。

デメリットは次のとおりです。

• より高い根では管理できなくなります。
• この方法では、不正確な推測や部分計算は許容されません。このようなエラーがあると、結果の次の桁がすべて間違ってしまいます。これは、近似エラーを自己修正するニュートン法とは異なります。
• 桁ごとの計算は理論上は十分効率的ですが、ソフトウェア実装にはコストがかかりすぎます。各反復には大きな数字が含まれ、より多くのメモリが必要になりますが、答えは正しい桁 1 つ分だけ進むだけです。したがって、アルゴリズムは桁が増えるごとに時間がかかります。

ネイピアの骨には、このアルゴリズムの実行を支援する機能が含まれています。シフトn乗根アルゴリズムは、この方法を一般化したものです。

まず、数Sの平方根を求めるケースを考えます。これは、10 を底とする 2 桁の数XYの平方です。ここで、Xは 10 の位、Y は1 の位です。具体的には、 S は3 桁または 4 桁の 10 進数で構成されます。 $${\displaystyle S=\left(10X+Y\right)^{2}=100X^{2}+20XY+Y^{2}.}$$

桁ごとのアルゴリズムを開始するために、Sの桁を右から順に 2 桁ずつ 2 つのグループに分割します。つまり、最初のグループは 1 桁または 2 桁になります。次に、Xの値を、 X ^{2 が}最初のグループ以下となる 最大の桁として決定します。次に、最初のグループとX ²の差を計算し、それに 2 番目のグループを連結して 2 番目の反復を開始します。これはSから減算することと同じで、 が残ります。 S' を10 で割り、次に2Xで割り、整数部分を保持してY を推測します。 2X を仮のYと連結し、 Yを掛けます。推測が正しければ、これは次を計算することと同じです。したがって、 S'と結果の差である剰余は0 になります。結果がS'より大きい場合は、推測値を 1 下げて、余りが 0 になるまで再試行します。これは答えが完全な平方根XYである単純なケースなので、アルゴリズムはここで停止します。 ${\displaystyle 100X^{2}}$${\displaystyle S'=20XY+Y^{2}}$$${\displaystyle (10(2X)+Y)Y=20XY+Y^{2}=S',}$$

同じ考え方は、任意の平方根計算にも適用できます。Sの平方根をn個の正の数の和として表すと、 $${\displaystyle S=\left(a_{1}+a_{2}+a_{3}+\dots +a_{n}\right)^{2}.}$$

基本的な恒等式を繰り返し適用することで、 右辺の項は次のように展開できる。 $${\displaystyle (x+y)^{2}=x^{2}+2xy+y^{2},}$$$${\displaystyle {\begin{aligned}&(a_{1}+a_{2}+a_{3}+\dotsb +a_{n})^{2}\\=&\,a_{1}^{2}+2a_{1}a_{2}+a_{2}^{2}+2(a_{1}+a_{2})a_{3}+a_{3}^{2}+\dots +a_{n-1}^{2}+2\left(\sum _{i=1}^{n-1}a_{i}\right)a_{n}+a_{n}^{2}\\=&\,a_{1}^{2}+[2a_{1}+a_{2}]a_{2}+[2(a_{1}+a_{2})+a_{3}]a_{3}+\dots +\left[2\left(\sum _{i=1}^{n-1}a_{i}\right)+a_{n}\right]a_{n}.\end{aligned}}}$$

この式では、s の値を順に推測することで平方根を求めることができます。数値がすでに推測されているとすると、上記の合計の右側のm番目の項は、 によって与えられます。ここで、 は、これまでに求められたおおよその平方根です。ここで、それぞれの新しい推測は 、の後のすべての項の合計、つまり剰余であり、 すべてに対してとなる、初期化時の を満たす必要があります。正確な平方根が求められた場合、そうでない場合は、 の合計が平方根の適切な近似値を与え、 は近似誤差です。 ${\displaystyle a_{i}}$${\displaystyle a_{1},\ldots ,a_{m-1}}$${\displaystyle Y_{m}=\left[2P_{m-1}+a_{m}\right]a_{m},}$${\textstyle P_{m-1}=\sum _{i=1}^{m-1}a_{i}}$${\displaystyle a_{m}}$$${\displaystyle X_{m}=X_{m-1}-Y_{m},}$$${\displaystyle X_{m}}$${\displaystyle Y_{m}}$${\displaystyle X_{m}\geq 0}$${\displaystyle 1\leq m\leq n,}$${\displaystyle X_{0}=S.}$${\displaystyle X_{n}=0,}$${\displaystyle a_{i}}$${\displaystyle X_{n}}$

例えば、10進数では、 は プレースホルダー で、係数はです。平方根計算の任意のm番目の段階で、これまでに求められた近似根と合計項は次のように与えられます。 $${\displaystyle S=\left(a_{1}\cdot 10^{n-1}+a_{2}\cdot 10^{n-2}+\cdots +a_{n-1}\cdot 10+a_{n}\right)^{2},}$$${\displaystyle 10^{n-i}}$${\displaystyle a_{i}\in \{0,1,2,\ldots ,9\}}$${\displaystyle P_{m-1}}$${\displaystyle Y_{m}}$$${\displaystyle P_{m-1}=\sum _{i=1}^{m-1}a_{i}\cdot 10^{n-i}=10^{n-m+1}\sum _{i=1}^{m-1}a_{i}\cdot 10^{m-i-1},}$$ $${\displaystyle Y_{m}=\left[2P_{m-1}+a_{m}\cdot 10^{n-m}\right]a_{m}\cdot 10^{n-m}=\left[20\sum _{i=1}^{m-1}a_{i}\cdot 10^{m-i-1}+a_{m}\right]a_{m}\cdot 10^{2(n-m)}.}$$

ここで、 の位の値は10 の偶数乗なので、任意の m 番目のステージで、 最初の項が である剰余 の最上位桁のペアのみを処理すれば済みます。以下のセクションでは、この手順を体系化します。${\displaystyle Y_{m}}$${\displaystyle X_{m-1}}$${\displaystyle Y_{m}}$

同様の方法を使用して、10 進数以外の記数法で平方根を計算できることは明らかです。たとえば、2 進数で桁ごとの平方根を求めることは、 の値が{0,1} のより小さな 2 進数セットから検索されるため、非常に効率的です。これにより、各段階で の値が の場合または の場合のいずれかになるため、計算が高速になります。 の可能な選択肢が 2 つしかないという事実は、計算のm番目の段階での値を決定するプロセスも容易にします。これは、 について かどうかを確認するだけでよいためです。この条件が満たされている場合は を取り、そうでない場合はを取ります。また、2 による乗算が左ビットシフトによって行われるという事実は、計算に役立ちます。 ${\displaystyle a_{i}}$${\displaystyle Y_{m}}$${\displaystyle Y_{m}=0}$${\displaystyle a_{m}=0}$${\displaystyle Y_{m}=2P_{m-1}+1}$${\displaystyle a_{m}=1}$${\displaystyle a_{m}}$${\displaystyle a_{m}}$${\displaystyle Y_{m}\leq X_{m-1}}$${\displaystyle a_{m}=1.}$${\displaystyle a_{m}=1}$${\displaystyle a_{m}=0.}$

元の数字を小数形式で書きます。数字は長除法のアルゴリズムに似た形式で書きます。長除法の場合と同様に、ルートは上の行に書きます。次に、小数点から始めて左と右の両方に数字をペアに分けます。ルートの小数点は、平方の小数点の上にあります。平方の各数字ペアの上には、ルートの 1 つの数字が表示されます。

左端の数字のペアから始めて、各ペアに対して次の手順を実行します。

1. 左から始めて、まだ使用されていない最上位 (左端) の数字のペアを下ろし (すべての数字が使用されている場合は、「00」と書きます)、前の手順の余りの右側に書き込みます (最初の手順では余りはありません)。つまり、余りに 100 を掛けて、2 つの数字を加算します。これが現在の値cになります。
2. 次のようにp、y、x を求めます。
   • 小数点を無視し、これまでに求めた根の部分をpとします。(最初のステップでは、 p = 0 です。)
   • となる最大の数字xを決定します。新しい変数y = x (20 p + x ) を使用します。 ${\displaystyle x(20p+x)\leq c}$
     • 注: 20 p + x は単にp を2 倍して、右側に数字xを追加したものです。
     • 注: x は、 c /(20· p ) を推測し、 yを試算して、必要に応じてx を上下に調整することで見つけることができます。
   • その数字をルートの次の数字、つまり先ほど下ろした平方数の 2 つの数字の上に置きます。したがって、次のp は古いp の10 倍にx を加えたものになります。${\displaystyle x}$
3. cからy を減算して新しい剰余を作成します。
4. 余りがゼロで、下げる桁がもうない場合は、アルゴリズムは終了します。それ以外の場合は、ステップ 1 に戻ってもう一度繰り返します。

152.2756 の平方根を求めます。

          1 2. 3 4
       /
     \/ 01 52.27 56

         01 1*1 <= 1 < 2*2 x=1
        01                     y = x*x = 1*1 = 1
         00 52 22*2 <= 52 < 23*3 x=2
        00 44                  y = (20+x)*x = 22*2 = 44
            08 27 243*3 <= 827 < 244*4 x=3
           07 29               y = (240+x)*x = 243*3 = 729
               98 56 2464*4 <= 9856 < 2465*5 x=4
              98 56            y = (2460+x)*x = 2464*4 = 9856
               00 00          アルゴリズム終了: 答え=12.34

このセクションでは、上記の桁ごとの計算セクションの形式論を使用しますが、わずかに変更して、 を各またはとともに使用します。から までの すべての を反復し、値が決定されたすべての の合計である近似解 を構築します。 が または に等しいかどうかを 判断するために、 とします。（つまり、 を含む近似解の平方がターゲットの平方を超えない場合）の場合は、それ以外の場合は および です。各ステップで 平方することを避けるために、差を保存し、で を設定することで増分的に更新します。最初は、で最大の を 設定します。 ${\displaystyle N^{2}=(a_{n}+\dotsb +a_{0})^{2}}$${\displaystyle a_{m}=2^{m}}$${\displaystyle a_{m}=0}$
${\displaystyle 2^{m}}$${\displaystyle 2^{n}}$${\displaystyle 2^{0}}$${\displaystyle P_{m}=a_{n}+a_{n-1}+\ldots +a_{m}}$${\displaystyle a_{i}}$
${\displaystyle a_{m}}$${\displaystyle 2^{m}}$${\displaystyle 0}$${\displaystyle P_{m}=P_{m+1}+2^{m}}$${\displaystyle P_{m}^{2}\leq N^{2}}$${\displaystyle 2^{m}}$${\displaystyle a_{m}=2^{m}}$${\displaystyle a_{m}=0}$${\displaystyle P_{m}=P_{m+1}}$
${\displaystyle P_{m}}$${\displaystyle X_{m}=N^{2}-P_{m}^{2}}$${\displaystyle X_{m}=X_{m+1}-Y_{m}}$${\displaystyle Y_{m}=P_{m}^{2}-P_{m+1}^{2}=2P_{m+1}a_{m}+a_{m}^{2}}$
${\displaystyle a_{n}=P_{n}=2^{n}}$${\displaystyle n}$${\displaystyle (2^{n})^{2}=4^{n}\leq N^{2}}$

追加の最適化として、がゼロでない場合の2 つの項であると を別々の変数、に格納します。 ${\displaystyle P_{m+1}2^{m+1}}$${\displaystyle (2^{m})^{2}}$${\displaystyle Y_{m}}$${\displaystyle a_{m}}$${\displaystyle c_{m}}$${\displaystyle d_{m}}$$${\displaystyle c_{m}=P_{m+1}2^{m+1}}$$ $${\displaystyle d_{m}=(2^{m})^{2}}$$ $${\displaystyle Y_{m}={\begin{cases}c_{m}+d_{m}&{\text{if }}a_{m}=2^{m}\\0&{\text{if }}a_{m}=0\end{cases}}}$$

${\displaystyle c_{m}}$各ステップで効率的に更新できます 。${\displaystyle d_{m}}$$${\displaystyle c_{m-1}=P_{m}2^{m}=(P_{m+1}+a_{m})2^{m}=P_{m+1}2^{m}+a_{m}2^{m}={\begin{cases}c_{m}/2+d_{m}&{\text{if }}a_{m}=2^{m}\\c_{m}/2&{\text{if }}a_{m}=0\end{cases}}}$$ $${\displaystyle d_{m-1}={\frac {d_{m}}{4}}}$$

注意してください: これは以下の関数で返される最終結果です。 $${\displaystyle c_{-1}=P_{0}2^{0}=P_{0}=N,}$$

このアルゴリズムのC言語での実装: ^[6]

int32_t isqrt ( int32_t n ) {   
    assert (( "sqrt 入力は負でない必要があります" 、n > 0 ));   

    // X_(n+1)
    int32_t x = n ;   

    // c_n
    int32_t c = 0 ;   

    // 4 の最大の累乗 <= n から始まる d_n
    int32_t d = 1 << 30 ; // 上から2番目のビットが設定されます。      
                         // ((unsigned) INT32_MAX + 1) / 2 と同じです。
    （d > n ）の間{    
        d >>= 2 ;  
    }

    // dₙ … d₀の場合
    （d != 0 ）の間{    
        if ( x >= c + d ) { // X_(m+1) ≥ Y_m の場合、a_m = 2^m            
            x -= c + d ; // X_m = X_(m+1) - Y_m            
            c = ( c >> 1 ) + d ; // c_(m-1) = c_m/2 + d_m (a_m は 2^m)        
        }
        それ以外{ 
            c >>= 1 ; // c_(m-1) = c_m/2 (aₘ は 0)             
        }
        d >>= 2 ; // d_(m-1) = d_m/4                 
    }
    c を返す; // c_(-1)                   
}

2進数や10進数、その他の基数でのより高速なアルゴリズムは、ルックアップテーブルを使用することで実現できます。つまり、より多くのストレージスペースと引き換えに実行時間を短縮することができます。^[7]

ポケット電卓には通常、指数関数と自然対数を計算するための優れたルーチンが実装されており、次に対数 ( ) と指数 ( )の特性を使用して見つかった恒等式を使用してSの平方根を計算します。 ^{[引用が必要]} 分数の分母はn乗根に対応します。上記のケースでは分母は 2 なので、この式は平方根を求めることを指定します。対数表や計算尺を使用して平方根を計算するときにも、同じ恒等式が使用されます。 ${\displaystyle \ln x^{n}=n\ln x}$${\displaystyle e^{\ln x}=x}$ $${\displaystyle {\sqrt {S}}=e^{{\frac {1}{2}}\ln S}.}$$

この方法は の平方根を求めるのに適用でき、 は に対して最もよく収束します。ただし、これはコンピュータベースの計算では実際の制限にはなりません。基数 2 の浮動小数点および固定小数点表現では、指数を変更するかシフトすることにより、それぞれ4 の整数乗、したがって対応する 2 の累乗を乗算するのは簡単です。したがって、 は範囲 に移動できます。さらに、次の方法では一般的な除算は使用せず、2 の累乗による加算、減算、乗算、および除算のみを使用します。これらも実装が簡単です。この方法の欠点は、バビロニア法などの単一変数反復法とは対照的に、数値誤差が蓄積することです。 ${\displaystyle 0<S<3\,\!}$${\displaystyle S\approx 1}$${\displaystyle S\,\!}$${\displaystyle {\sqrt {S}}}$${\displaystyle S\,\!}$${\textstyle {\tfrac {1}{2}}\leq S<2}$

このメソッドの初期化ステップは、 反復ステップが 次に(while ) を読み取りながら行われます。 $${\displaystyle {\begin{aligned}a_{0}&=S\\c_{0}&=S-1\end{aligned}}}$$$${\displaystyle {\begin{aligned}a_{n+1}&=a_{n}-a_{n}c_{n}/2\\c_{n+1}&=c_{n}^{2}(c_{n}-3)/4\end{aligned}}}$$${\displaystyle a_{n}\to {\sqrt {S}}}$${\displaystyle c_{n}\to 0}$

の収束は2 次式であり、したがって の収束も2 次式です。 ${\displaystyle c_{n}\,\!}$${\displaystyle a_{n}\,\!}$

この方法の証明は比較的簡単です。まず、 の反復定義を として書き直します。 次に、 を帰納的に証明するのは簡単です 。したがって、 が目的の結果に 収束することは、が 0 に収束することによって保証され、これは から導かれます。 ${\displaystyle c_{n}}$$${\displaystyle 1+c_{n+1}=(1+c_{n})(1-{\tfrac {1}{2}}c_{n})^{2}.}$$$${\displaystyle S(1+c_{n})=a_{n}^{2}}$$${\displaystyle a_{n}\,\!}$${\displaystyle {\sqrt {S}}}$${\displaystyle c_{n}\,\!}$${\displaystyle -1<c_{0}<2\,\!}$