級数に基づく多数桁計算の演算量削減を実現する分割有理数化法

概要

論文の詳細を見る
ベキ級数で表現される関数に対して, n桁の精度でその値を計算する方法を提案する.この方法は, 分割統治法に基づくので分割有理数化法(Divide and Rationalize Method, DRM法)と名付けるが, 従来の計算量を改善するものである.n桁の乗算の演算量をM(n)とするとき, 入力値がO(1)桁の有理数の場合, DRM法により計算量をO(n^2)からO(M(n)・(log_2n)^2)以下にできる.また, 入力値がn桁の精度で関数に加法定理が適用できる場合には, 計算量をO(M(n)・n)からO(M(n)・(log_2n)^3)以下に削減する.このDRM法は2つの方法から構成される.第1の方法は級数の和の計算にトーナメント方式を適用し2項ずつ通分して有理数化し, 除算でn桁精度の実数にする方式である.第2の方法はn桁精度の入力値Xを分母の桁数が上位桁からα, 2α, 4α, …, 2^<p-1>α桁ずつの有理数に分離し, 各分割ごとに関数値を計算し, それらから加法定理を用いてXでの関数値を計算する方式である.本方法は関数の多数桁計算で著名なBrentのアルゴリズムより適用範囲が広く, 連分数の計算や基底変換にも適用可能で, アルゴリズムはより単純で分かりやすい.また, 並列処理に向いており, 計算桁数を増加するとき計算済みの有理数が再利用可能である.
一般社団法人情報処理学会の論文
2000-06-15

級数に基づく多数桁計算の演算量削減を実現する分割有理数化法

スポンサーリンク

概要

著者

関連論文

スポンサーリンク