多倍長演算のための平方根の高速計算法
スポンサーリンク
概要
- 論文の詳細を見る
本論文では,平方根を近似する高次収束法のアルゴリズム群を提案し,それらの多倍長演算における計算方法と計算効率について考察している.ここで提案されたアルゴリズム群は,収束の次数を任意に高く取ることができ,また初期値に無関係に収束するという特徴を持っている.このアルゴリズム群は,特別な場合として収束の次数が2の場合はニュートン法になり,3の場合はBailey法となる.反復関数はどの場合も有理関数となり,この有理関数を多倍長演算でより高速に計算するため,いくつかの計算方法を提案している.ここで提案された計算法の時間計算量を詳細に検討した結果,常に一定の桁数で計算する「固定長演算」では,多倍長数の平方根を計算するときは,5次収束法を2次因子に分解する方法が最も高速であり,単長数(単精度数)の平方根を計算するときは,平方根の逆数に2次収束する方法が最も高速であることが判明した.一方,計算桁数を反復値の精度に応じて変更していく「可変長演算」でも,平方根の逆数に2次収束する方法が最も高速であることが判明した.また「可変長演算」では,いかなる次数の解法あるいはいかなる計算法を用いたとしても,「固定長演算」で計算した場合の高々反復2回分で計算が完了するという結論も得られいる.以上の結論は,これまでに知られているどのような乗算法にも妥当するものである.
- 一般社団法人情報処理学会の論文
- 1990-07-15
著者
関連論文
- 平方根を計算する高次収束法とその計算量の比較:$0(n^2)$の高速除算法による計算に関して(数値解析と科学計算)
- 多倍長演算のための平方根の高速計算法
- n乗根の連分数展開と誤差評価II
- On the Existence Theorems of BDF and Adams type Second Derivative BDF with Nonnegative Coefficients
- 非負係数を持つ線形多段階法の存在条件(常微分方程式の数値解法)
- 浮動小数点演算における絶対丸め誤差のモーメントの存在とその推定
- 浮動小数点演算における相対丸め誤差の平均と分散について
- 実数値の浮動小数点表現における仮数の分布と下位桁の漸近的性質