級数に基づく多数桁計算の演算量削減を実現する分割有理数化法 A Divide and Rationalize Method which Improves the Multiple-precision Function Computation with Series Expansion

この論文にアクセスする

この論文をさがす

著者

抄録

ベキ級数で表現される関数に対して,$n$ 桁の精度でその値を計算する方法を提案する.この方法は,分割統治法に基づくので分割有理数化法(Divide and Rationalize Method,DRM法)と名付けるが,従来の計算量を改善するものである.$n$ 桁の乗算の演算量を $M(n)$ とするとき,入力値が $O(1)$ 桁の有理数の場合,DRM法により計算量を $O(n^2)$ から $O(M(n)?cdot (?log_2n)^2)$ 以下にできる.また,入力値が $n$ 桁の精度で関数に加法定理が適用できる場合には,計算量を $O(M(n) ?cdot n)$ から $O(M(n)?cdot (?log_2n)^3)$ 以下に削減する.このDRM法は2つの方法から構成される.第1の方法は級数の和の計算にトーナメント方式を適用し2項ずつ通分して有理数化し,除算で $n$ 桁精度の実数にする方式である.第2の方法は $n$ 桁精度の入力値 $X$ を分母の桁数が上位桁から $?alpha 2?alpha 4?alpha ?cdots 2^{p-1}?alpha$ 桁ずつの有理数に分解し,各分割ごとに関数値を計算し,それらから加法定理を用いて $X$ での関数値を計算する方式である.本方法は関数の多数桁計算で著名なBrentのアルゴリズムより適用範囲が広く,連分数の計算や基底変換にも適用可能で,アルゴリズムはより単純で分かりやすい.また,並列処理に向いており,計算桁数を増加するとき計算済みの有理数が再利用可能である.We propose a new divide and conquer method for $n$-digit evaluation offunctions expressed by power series.The method which we call Divide andRationalize Method (DRM) improves the conventional computing complexity.In the case of the input precision with an $O(1)$-digit rational number,the method reduces the complexity of $n$-digit function computation from $O(n^2)$ to $O(M(n)\cdot (\log_2n)^2)$ or below.In the case of the input precisionwith an $n$-digit real number and possible to use the additiontheorem, the method reduces the $n$-digit function computation from $O(M(n) \cdot n)$ to $O(M(n) \cdot (\log_2n)^3)$ or below, where $M(n)$ is the number of computation operations required to multiply $n$-digit precision numbers.The DRM consists of two methods.The first method is a method which sums up from each rational numbersin the series to $n$-digit rational numbers with tournamentmethod.The second method is a method which computes a value of the functionfor each digit corresponding to an input value of rational numberwith $\alpha, 2\alpha, 4\alpha, \cdots, 2^{p-1}\alpha$ digitdenominator from the higher digit and sums the value of the functionaccording to the addition theorem.The coverage of the proposed method is wider in the multiple-precisionfunction computation than Brent's algorithm and it can be applicableto radix conversion and computation of continued fractions.Also, it is suitable for the parallel processing and possible to reuseintermediate rational results for more higher precision computation.

We propose a new divide and conquer method for n-digit evaluation of functions expressed by power series. The method which we call Divide and Rationalize Method(DRM) improves the conventional computing complexity. In the case of the input precision with an O(1)-digit rational number, the method reduces the complexity of n-digit function computation from O(n^2)to O(M(n)・(log_n)^2)or below. In the case of the input precision with an n-digit real number and possible to use the addition theorem, the method reduces the n-digit function computation from O(M(n)・n)to O(M(n)・(log_2n)^3)or below, where M(n)is the number of computation operations required to multiply n-digit precision numbers. The DRM consists of two methods. The first method is a method which sums up from each rational numbers in the series to n-digit rational numbers with tournament method. The second method is a method which computes a value of the function for each digit corresponding to an input value of rational number with α, 2α, 4α, …, 2^<p-1>α digit denominator from the higher digit and sums the value of the function according to the addition theorem. The coverage of the proposed method is wider in the multiple-precision function computation than Brent's algorithm and it can be applicable to radix conversion and computation of continued fractions. Also, it is suitable for the parallel processing and possible to reuse intermediate rational results for more higher precision computation.

収録刊行物

  • 情報処理学会論文誌

    情報処理学会論文誌 41(6), 1811-1819, 2000-06-15

    一般社団法人情報処理学会

参考文献:  9件中 1-9件 を表示

被引用文献:  2件中 1-2件 を表示

各種コード

  • NII論文ID(NAID)
    110002725372
  • NII書誌ID(NCID)
    AN00116647
  • 本文言語コード
    JPN
  • 資料種別
    Journal Article
  • ISSN
    1882-7764
  • NDL 記事登録ID
    5370333
  • NDL 雑誌分類
    ZM13(科学技術--科学技術一般--データ処理・計算機)
  • NDL 請求記号
    Z14-741
  • データ提供元
    CJP書誌  CJP引用  NDL  NII-ELS  IR  IPSJ 
ページトップへ