早いsqrtの計算法

早いsqrtの計算法

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