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

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

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} \]

この再定義された数列 $\{A_j\}$、$\{C_j\}$、$\{D_j\}$ を用いると $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) \left(\frac{y}{x}\right)^\gamma \]

と表される。 この変形により保存、計算する数列を 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. \]

となり $(A_k, C_k, D_k)$ と $(A_{k+1}, C_{k+1}, D_{k+1})$ を $(A_kD_{k+1}+A_{k+1}C_k, C_kC_{k+1}, D_kD_{k+1})$ に纏めることができた。

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