早いsqrtの計算法

早いsqrtの計算法

$x$が1兆桁ならまず1兆で割る。
その結果を$y$とする。
計算結果を$a$とすると$a=100万*\sqrt{y}$。
今度は4で割っていく。
割られた結果を$z_1, z_2, \cdots, z_n$とすると、$a=(100万*2^n)*\sqrt{z_n}$
$\sqrt{z_n}$を求める時は、例えば$2< z_n<3$なら$\sqrt{2.5}$を計算して二分探索で求める。(既知の値でない場合)
二分探索じゃなくて$1/10$位に区間を分割した方が人間に分かりやすいのでは、とお考えになる向きもあるでしょうが、二分探索はコンピュータにも人間にも実は一番計算しやすいです。
例えば
$\begin{eqnarray}&\sqrt{2.5}&=\sqrt{10/4}\\ &&=\sqrt{\frac{10}{4}}\\ &&=\frac{\sqrt{10}}{2} \end{eqnarray}$
こんな感じで分母が整数になるなどのメリットがあります。