\documentclass{jsarticle}
\begin{document}
\section*{平方根の2進数表記を得る開平}
正の実数$x$の正の平方根$\sqrt{x}$を2進数で表記した時、
第$i$位、つまり$2^i$の桁の値を$b_i$とする。
すなわち、
\begin{eqnarray*}
\sqrt{x} = \sum_{i \in \mathbf{Z}} b_i 2^i
\end{eqnarray*}
今、第$m$位より上位の桁$b_i \ (i > m)$が全て既知であるとする。
上式の右辺をこの第$m$位とその上位と下位の項で分ける。
\begin{eqnarray*}
\sqrt{x} &=& \sum_{i > m} b_i 2^i + b_m 2^m + \sum_{i < m} b_i 2^i \\
2^{-m} \sqrt{x} &=& \sum_{i > m} b_i 2^{i-m} + b_m + \sum_{i < m} b_i 2^{i-m}
\end{eqnarray*}
ここで、左辺を$y_m$、右辺第1項を$a_m$、右辺第3項を$c_m$と置く。
\begin{eqnarray*}
y_m = a_m + b_m + c_m
\end{eqnarray*}
定義から明らかに$a_m + b_m$は$y_m$の整数部、$c_m$は小数部である。
したがって、$0 \le c_m < 1$であることから次の不等式が成立する。
\begin{eqnarray*}
a_m + b_m \le y_m < a_m + b_m + 1
\end{eqnarray*}
さらに、$b_m$は0であるか1であるかであり、
\begin{eqnarray*}
b_m = \left\{
\begin{array}{lll}
0 & \mbox{when} & a_m \le y_m < a_m + 1 \\
1 & \mbox{when} & a_m + 1 \le y_m < a_m + 2
\end{array}
\right.
\end{eqnarray*}
つまり、$b_m$は$y_m$と$a_m + 1$を比較することで求められる。
上式を整理すると、
\begin{eqnarray*}
b_m = \left\{
\begin{array}{lll}
0 & \mbox{when} & y_m < a_m + 1 \\
1 & \mbox{when} & y_m \ge a_m + 1
\end{array}
\right.
\end{eqnarray*}
ところが、$y_m$はまさに求めようとしている$\sqrt{x}$を含んでいる。
そこで、$y_m$と$a_m + 1$を比較するのではなく、
それぞれを2乗した値を比較する。
\begin{eqnarray*}
b_m = \left\{
\begin{array}{lll}
0 & \mbox{when} & z_m < (a_m + 1)^2 \\
1 & \mbox{when} & z_m \ge (a_m + 1)^2
\end{array}
\right.
\end{eqnarray*}
ここで、$z_m = y_m^2 = 2^{-2m} x$である。
以上が未知の桁の最上位$b_m$を$x$と既知の桁$b_i \ (i > m)$から求める方法である。
次に、最初は全てが未知である各桁を求めていく手順について考える。
明らかに、$b_n = 1$かつ$b_i = 0 \ ({}^\forall i > n)$であるような整数$n$が存在する。
この時、
\begin{eqnarray*}
y_n = a_n + b_n + c_n = 0 + 1 + c_n = 1 + c_n
\end{eqnarray*}
$1 \le 1 + c_n < 2$であるので、以下の不等式が成り立つ。
\begin{eqnarray*}
1 \le z_n = y_n^2 = (1 + c_n)^2 < 4
\end{eqnarray*}
したがって、$1 \le 2^{-2n} x < 4$となるような整数$n$を見つければよい。
底が2の対数をとれば、
\begin{eqnarray*}
& 0 \le -2n + \log_2 x < 2 \\
& 0.5 \log_2 x \ge n > 0.5 \log_2 x - 1
\end{eqnarray*}
であるので$n$は一意に決まる。
$n$が得られれば、第$n$位以上の桁の値は全て既知となり、
\begin{eqnarray*}
a_n = 0,\ b_n = 1,\ z_n = 2^{-2n} x
\end{eqnarray*}
を初期値として、これより下位の桁を順次求めていくことができる。
$a_m$の定義から、
\begin{eqnarray*}
a_m &=& \sum_{i > m} b_i 2^{i-m} \\
&=& \sum_{i > m+1} b_i 2^{i-m} + b_{m+1} 2^{(m+1)-m} \\
&=& 2 \sum_{i > m+1} b_i 2^{i-(m+1)} + 2 b_{m+1} \\
&=& 2 a_{m+1} + 2 b_{m+1} \\
&=& 2 (a_{m+1} + b_{m+1})
\end{eqnarray*}
なる漸化式を導ける。また、$z_m$の定義から、
\begin{eqnarray*}
z_m = 2^{-2m} x = 4 \cdot 2^{-2(m+1)} x = 4 z_{m+1}
\end{eqnarray*}
である。
先述の第$n$位の桁を初期値として、これらの漸化式を使い、
$z_m$と$(a_m + 1)^2$の比較から$b_m$を順次求めていけば
任意の桁までの$\sqrt{x}$の2進数表記が得られることになる。
\end{document}
