円周率.jp (http://xn--w6q13e505b.jp/method/drm.html)

DRM 法

分割有理数化法(DRM;Divide and Rationalize Method) [JT02][JT03] は基本的には Binary Splitting Method と同じであるが,包括的なまとめ方がなされていて適用範囲が広い.

なお,細かいことではあるが DRM 法の M は「法」の意味なので 「DRM 法」というのは重畳である.

概要

DRM 法は

\[ \begin{eqnarray} f\left(\dfrac{y}{x}\right) &=& \sum_{j=0}^{n-1} \dfrac{a_j}{b_j} \left( \prod_{k=0}^j \dfrac{c_k}{d_k} \right) \left( \dfrac{y}{x} \right)^{\gamma + \beta j}\\ &=& \dfrac{c_0}{d_0} \dfrac{Y}{X} \left( \dfrac{a_0}{b_0} + \dfrac{c_1}{d_1} \dfrac{Y}{X} \left( \dfrac{a_1}{b_1} + \dfrac{c_2}{d_2} \dfrac{Y}{X} \left( \dfrac{a_2}{b_2} + \cdots \dfrac{c_{n-1}}{d_{n-1}} \left( \dfrac{a_{n-1}}{b_{n-1}} \right) \cdots \right) \right) \right) \left(\dfrac{y}{x}\right)^{\gamma} \end{eqnarray} \]

の形で表される有理関数を, トーナメント式に括弧を外していくことで計算する方式である. なお略記のため $Y=y^\beta$,$X=x^\beta$ と置き換えた. 1 組の括弧を外すために

\[ \cdots + \frac{c_k}{d_k}\frac{Y}{X} \left( \frac{a_k}{b_k} + \frac{c_{k+1}}{d_{k+1}} \frac{Y}{X} \left( \frac{a_{k+1}}{b_{k+1}} + \frac{c_{k+2}}{d_{k+2}} \frac{Y}{X} \left( \frac{a_{k+2}}{b_{k+2}} + \cdots \right. \right. \right. \] \[ \cdots + \frac{c_k}{d_k} \frac{Y}{X} \left( \frac{a_k}{b_k} + \frac{c_{k+1}}{d_{k+1}} \frac{Y}{X} \frac{a_{k+1}}{b_{k+1}} + \frac{c_{k+1}}{d_{k+1}}\frac{c_{k+2}}{d_{k+2}} \left( \frac{Y}{X} \right)^2 \left( \frac{a_{k+2}}{b_{k+2}} + \cdots \right. \right. \] \[ \cdots + \frac{c_k}{d_k} \frac{Y}{X} \left( \frac{a_kd_{k+1}b_{k+1}X+b_kc_{k+1}a_{k+1}Y}{b_kb_{k+1}d_{k+1}X} + \frac{c_{k+1}}{d_{k+1}}\frac{c_{k+2}}{d_{k+2}} \left(\frac{Y}{X}\right)^2 \left( \frac{a_{k+2}}{b_{k+2}} + \cdots \right. \right. \]

という段階を踏むことになる. この展開を 1 個置きに適用させると括弧の数 ($Y/X$ を囲っているものはカウントしない) が半分になり,各要素に入る値の桁数が2〜3倍になる.

簡易化

上記の公式で計算を行っていく時,計算中に値を保持しておくべき数列が 4 列 ($\{a_k\}$, $\{b_k\}$, $\{c_k\}$, $\{d_k\}$) あるためあまり効率的ではない. そこで,以下のような変形を行うことで計算量を削減する.

\[ \begin{cases} A_0 = a_0 c_0\\ A_k = a_k \end{cases},\ \begin{cases} C_0 = c_1 b_0 y^\beta\\ C_k = c_{k+1} b_k y^\beta \end{cases},\ \begin{cases} D_0 = d_0 b_0\\ D_k = d_k b_k x^\beta \end{cases} \]

この再定義された数列 AjCjDj を用いると, f(y/x) は

\[ \left(\frac{y}{x}\right)^\gamma \sum_{j=0}^{n-1} A_j \left(\prod_{k=0}^{j} \frac{C_k}{D_k}\right) = \frac{1}{D_0} \left( A_0 + \frac{C_0}{D_1} \left( A_1 + \frac{C_1}{D_2} \left( A_2 + \cdots \frac{c_{n-2}}{d_{n-1}} \left( A_{n-1} \right) \cdots \right) \right) \right) \]

と表される. この変形により保存,計算する数列を 3 列に減らすことができる. [JT01] これを上記と同様に展開すると

\[ \cdots + \frac{C_{k-1}}{D_k} \left( A_k + \frac{C_k}{D_{k+1}} \left( A_{k+1} + \frac{C_{k+1}}{D_{k+2}} \left( A_{k+2} + \cdots \right. \right. \right. \] \[ \cdots + \frac{C_{k-1}}{D_k} \left( A_k + \frac{C_k}{D_{k+1}} A_{k+1} + \frac{C_k}{D_{k+1}} \frac{C_{k+1}}{D_{k+2}} \left( A_{k+2} + \cdots \right. \right. \] \[ \cdots + \frac{C_{k-1}}{D_k} \left( \frac{A_kD_{k+1}+C_kA_{k+1}}{D_{k+1}} + \frac{C_k}{D_{k+1}}\frac{C_{k+1}}{D_{k+2}} \left( A_{k+2} + \cdots \right. \right. \] \[ \cdots + \frac{C_{k-1}}{D_kD_{k+1}} \left( (A_k D_{k+1} + C_k A_{k+1}) + \frac{C_kC_{k+1}}{D_{k+2}} \left( A_{k+2} + \cdots \right. \right. \]

となり (AkCkDk) と (Ak+1Ck+1Dk+1) を (AkDk+1Ak+1CkCkCk+1DkDk+1) に纏めることができた.

上の例と同様に, 1 つ置きの括弧を同時に外す作業を繰り返すことで項数が半減し, 各要素の桁数が 2 倍になるのは自明である.