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

• Item type: Journal(1)
• 公開日: 2000-06-15
• タイトル: 級数に基づく多数桁計算の演算量削減を実現する分割有理数化法
• タイトル / 言語: en
• タイトル: A Divide and Rationalize Method which Improves the Multiple-precision Function Computation with Series Expansion
• 言語: jpn
• キーワード / 主題Scheme: Other
• キーワード / 主題: 論文
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_6501
• 資源タイプ: journal article
• その他タイトル / その他のタイトル: 数値計算
• 著者所属: 株式会社日立製作所エンタープライズサーバ事業部
• 著者所属: 東京大学情報基盤センター
• 著者所属: 東京大学情報基盤センター／現在，埼玉大学大学院理工学研究科
• 著者所属(英): en
• 著者所属(英): Enterprise Server Division, Hitachi Ltd.
• 著者所属(英): en
• 著者所属(英): Information Technology Center, University of Tokyo
• 著者所属(英): en
• 著者所属(英): Information Technology Center, University of Tokyo/Presently with Graduate School of Science and Engineering, Saitama University
• 著者名: 後, 保範; 金田, 康正; 高橋, 大介
• 著者名(英): Yasunori, Ushiro; Yasumasa, Kanada; Daisuke, Takahashi
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: ベキ級数で表現される関数に対して，$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のアルゴリズムより適用範囲が広く，連分数の計算や基底変換にも適用可能で，アルゴリズムはより単純で分かりやすい．また，並列処理に向いており，計算桁数を増加するとき計算済みの有理数が再利用可能である．
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: 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.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN00116647
• 書誌情報: 情報処理学会論文誌; 巻 41, 号 6, p. 1811-1819, 発行日 2000-06-15
• ISSN / 収録物識別子タイプ: ISSN
• ISSN / 収録物識別子: 1882-7764