平方根アルゴリズム

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

（コンピュータが内部的に行っているように）バイナリ数体系で作業する場合、 Sを次のように表現します。$\displaystyle a\times 2^{2n}}$どこ$0.1_2 ≤ a < 10_2$平方根$\displaystyle {\sqrt {S}}={\sqrt {a}}\times 2^{n}}$推定値として $$${\displaystyle {\sqrt {S}}\approx (0.485+0.485a)\cdot 2^{n}}$$$

これは、有効数字3桁の係数を持つ最小二乗回帰直線です。${\displaystyle {\sqrt {a}}}$最大絶対誤差は0.0408です。${\displaystyle a=2}$最大相対誤差は3.0%で、${\displaystyle a=1}$計算上都合の良い丸め推定値（係数が2のべき乗であるため）は次のとおりです。

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

これは、2 で最大絶対誤差が 0.086、a = 0.5およびa = 2.0で最大相対誤差が 6.1% である。

のために$${\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.5a)\cdot 2^{8}=1.0111\;0100\;1101\;0010_{2}\times 1\;0000\;0000_{2}=1.456\times 256=372.8.}$$$\displaystyle {\sqrt {125348}}=354.0}$したがって、推定値の絶対誤差は19、相対誤差は5.3%です。相対誤差は1/2 ⁴よりわずかに小さいので、推定値は4ビット以上まで正確です。

8 ビットの精度での推定値は、の上位 8 ビットのテーブルを参照することで取得できます。ただし、ほとんどの浮動小数点表現では上位ビットが暗黙的に含まれており、8 ビットの下位ビットは丸められることに注意してください。テーブルは、事前に計算された 8 ビットの平方根値の 256 バイトです。たとえば、1.8515625 _{10を表すインデックス 11101101 2}の場合、エントリは1.359375 ₁₀を表し、1.8515625 ₁₀の8 ビット精度 (2 桁以上の小数点以下)での平方根です_。

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

より正確には、${\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 {\ Sx^{2}\ }{\ 2x+\varepsilon \ }}\approx {\frac {\ Sx^{2}\ }{2x}}\ ,}$もし私たちが次のように仮定するならば${\displaystyle \ \varepsilon \ll x~}$

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

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

仮に${\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 S=125348}$ヘロン法の例と同様に、最初の反復では $${\displaystyle {\begin{alignedat}{3}x_{0}&=600\\[1ex]a_{0}&={\frac {125348-600^{2}}{2\times 600}}&&=-195.5433\approx -200\\[1ex]x_{1}&=600+(-200)&&={\phantom {-}}400\\[1ex]x_{2}&=400-{\frac {(-200)^{2}}{2\times 400}}&&={\phantom {-}}350\end{alignedat}}}$$

同様に、2回目の反復では $${\displaystyle {\begin{alignedat}{3}a_{2}&={\frac {125348-350^{2}}{2\times 350}}&&={\phantom {00}}4.06857\\[1ex]x_{3}&=350+4.06857&&=354.06857\\[1ex]x_{4}&=354.06857-{\frac {4.06857^{2}}{2\times 354.06857}}&&=354.045194\end{alignedat}}}$$ ヘロンの方法とは異なり、${\displaystyle x_{3}}$は8桁まで計算する必要があります。なぜなら、${\displaystyle x_{4}}$のエラーを修正しません${\displaystyle x_{3}}$。

まず、数Sの平方根を求める場合を考えてみましょう。これは、10進数2桁XYの平方根です。ここで、Xは十の位、Yは一の位です。具体的には次のようになります。 $${\displaystyle S=\left(10X+Y\right)^{2}=100X^{2}+20XY+Y^{2}.}$$Sは3桁または4桁の小数点で構成されます。

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

同じ考え方を、次に任意の平方根の計算に拡張できます。S をn個の正の数 の和として表すことで、Sの平方根を見つけることができると仮定します。$${\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}}}$$

この式を使うと、次の値を順に推測することで平方根を求めることができます。${\displaystyle a_{i}}$s. 数字が${\displaystyle a_{1},\ldots ,a_{m-1}}$が既に推測されている場合、上記の総和の右辺のm番目の項は次のように与えられます。${\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}}$s は平方根の適切な近似値を与え、${\displaystyle X_{n}}$は近似誤差である。

例えば、十進数システムでは $${\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},}$$ どこ$10ni$はプレースホルダーであり、係数です。${\displaystyle a_{i}\in \{0,1,2,\ldots ,9\}}$平方根計算の任意の m 番目の段階では、これまでに見つかった近似根は、${\displaystyle P_{m-1}}$そして総和項${\displaystyle Y_{m}}$は次のように与えられる。 $${\displaystyle P_{m-1}=\sum _{i=1}^{m-1}a_{i}\cdot 10^{ni}=10^{n-m+1}\sum _{i=1}^{m-1}a_{i}\cdot 10^{mi-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)}.}$$

ここでは位取りが${\displaystyle Y_{m}}$が10の偶数乗である場合、余りの最上位2桁のみを扱えばよい。${\displaystyle X_{m-1}}$その最初の項は${\displaystyle Y_{m}}$任意のm番目の段階において。以下のセクションではこの手順を体系化します。

10進数以外の数体系でも平方根を計算するのに同様の方法が使えることは明らかです。例えば、2進数体系で桁ごとの平方根を求めるのは非常に効率的です。なぜなら、${\displaystyle a_{i}}$は、より小さなバイナリ数字のセット {0,1} から検索されます。これにより、各段階での値が${\displaystyle Y_{m}}$どちらか${\displaystyle Y_{m}=0}$のために${\displaystyle a_{m}=0}$または${\displaystyle Y_{m}=2P_{m-1}+1}$のために${\displaystyle a_{m}=1}$私たちには2つの選択肢しかないという事実${\displaystyle a_{m}}$また、価値を決定するプロセスも${\displaystyle a_{m}}$m番目の計算段階では、より簡単になります。これは、次のことを確認するだけでよいからです。${\displaystyle Y_{m}\leq X_{m-1}}$のために${\displaystyle a_{m}=1.}$この条件が満たされる場合、${\displaystyle a_{m}=1}$; そうでない場合は${\displaystyle a_{m}=0.}$また、2倍の演算が左ビットシフトによって行われるという事実も、計算を有利にする。

元の数を10進数で書きます。数字の書き方は筆算のアルゴリズムに似ており、筆算と同様に、平方根は上の行に書きます。次に、小数点から始めて左右に桁を2桁ずつに分けます。平方根の小数点は、平方数の小数点の上にきます。平方根の1桁は、平方数の各桁のペアの上に表示されます。

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

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

 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}}$。

追加の最適化として、${\displaystyle P_{m+1}2^{m+1}}$そして${\displaystyle (2^{m})^{2}}$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,}$$これは、以下の関数で返される最終結果です。