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

摘要

ベキ級数で表現される関数に対して，$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 $lpha, 2lpha, 4lpha, cdots, 2^{p-1}lpha$ 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 Brentu27s 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.