|
数学関数 |
|
平方根 |
| 最終更新日：2006/07/03 書き直し |
●概要
除算を逆数法で行っても、あいかわらず、除算は乗算に比べて数倍以上遅い。従って、開根(平方、立方など)を行うニュートン法の漸化式に現われる多倍長除算(以下参照)を排除すれば、数倍の高速化が期待できる。
通常、Y = X2 - a とし、漸化式を
Xn+1 = Xn - 1 / 2 * (X2 - a) / X
となり、漸化式に逆数あるいは除算が現われ、速度的に不利となる。
●原理
根の逆数を求めることにすれば、関数は、
f(X) = 1 / Xm - a
となる。平方根なので m は 2 となる。これを、漸化式にすると、
Xn+1 = Xn - (1 / 2) * Xn * (a * Xn2 - 1)
となる。ここには、多倍長同士の除算は含まれていない。多倍長/Integer なる除算はあるが、これは速い。また、δ = X * (a * X2 - 1) とすれば、収束条件にもなる。
●方法
求めた、X を、a倍すれば、aの平方根となる。ついでに、X を、平方根の逆数として、ReciproSqrt関数にしている。
漸化式の早い収束を図るため、以下のようにしている。当然、実際に求めるのは仮数部のみである。
X = M * 10P
であるから、
・P = 2 *n のとき
Srqt(X) = Sqrt(M) * 10n
・P = 2 *n + 1 のとき
Srqt(X) = Sqrt(10 * M) * 10n
なので、赤の部分をニュートン法で算出する。但し、X の指数部の符号で若干処理は異なる。
●高速化
ニュートン法にてまとめて解説しているので、ここでは結果のみ掲げる。
○単一初期値予測
初期値による平方根(逆数)の演算時間を専用ツールにてシミュレーションすると、下図のようになった。
3列目は初期値15桁の場合の基準演算時間、その右側に、列見出しの値を初期値にした演算時間である。薄緑色の時間は、その目標精度での最小値である。これによれば、概ね、目標精度の1/4か1/8の精度の初期値で求めた時間が最小となり、基準時間の1/2から1/3に改善されることが分かる。当初、初期値精度を512桁と固定していたが、本法の方が改善できる。
○多段初期値予測
実測は時間が掛かるので、同じく専用ツールでシミュレーションして見た。 結果は下図。
列見出しの15 は、基準時間、単一(1/8) は、目標精度の1/8 の初期値精度で求めた時間、1/4単位は、目標精度の1/4m 系列の初期値、1/8単位は、目標精度の1/8m 系列の初期値で求めた時間である。
シミュレーション結果では、1/4単位方式が単一方式より時間が20%〜25%程度短くなる。
●実測値
実際に演算した結果を下図に示す。逆数を元に戻す演算時間も含んでいる。
