円周率.jp > 多数桁計算 > DRM 法

DRM 法

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

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

概要

DRM 法は

f \Bigl(\frac{y}{x}\Bigr) \sum_{j=0}%5e{n-1} \frac{a_j}{b_j} \Bigl(\prod_{k=0}%5e{j} \frac{c_k}{d_k}\Bigr) \Bigl(\frac{y}{x}\Bigr) γ+β j
\frac{c_0}{d_0} \frac{Y}{X} \Bigl( \frac{a_0}{b_0}\frac{c_1}{d_1} \frac{Y}{X} \Bigl( \frac{a_1}{b_1}\frac{c_2}{d_2} \frac{Y}{X} \Bigl( \frac{a_2}{b_2} + … \frac{c_{n-1}}{d_{n-1}} \Bigl( \frac{a_{n-1}}{b_{n-1}} \frac{Y}{X} \Bigr)\Bigr) \Bigr) \Bigr)

の形で表される有理関数を, トーナメント式に括弧を外していくことで計算する方式である. なお略記のため YyβXxβ と置き換えた. 1 組みの括弧を外すために

… + \frac{c_k}{d_k} \frac{Y}{X} \Bigl( \frac{a_k}{b_k}\frac{c_{k+1}}{d_{k+1}} \frac{Y}{X} \Bigl( \frac{a_{k+1}}{b_{k+1}}\frac{c_{k+2}}{d_{k+2}} \frac{Y}{X} \Bigl( \frac{a_{k+2}}{b_{k+2}} + …
… + \frac{c_k}{d_k} \frac{Y}{X} \Bigl( \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}} \Bigl(\frac{Y}{X}\Bigr)2 \Bigl( \frac{a_{k+2}}{b_{k+2}} + …
… + \frac{c_k}{d_k} \frac{Y}{X} \Bigl( \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}} \Bigl(\frac{Y}{X}\Bigr)2 \Bigl( \frac{a_{k+2}}{b_{k+2}} + …

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

簡易化

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

A0a0 c0 C0c1 b0 yβ D0d0 b0
Akak Ckck+1 bk yβ Dkdk bk xβ   (for k≧1)

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

\Bigl(\frac{y}{x}\Bigr) γ \sum_{j=0}%5e{n-1} Aj \Bigl(\prod_{k=0}%5e{j} \frac{C_k}{D_k}\Bigr)\frac{1}{D_0} \Bigl( A0\frac{C_0}{D_1} \Bigl( A1\frac{C_1}{D_2} \Bigl( A2 + … \frac{c_{n-2}}{d_{n-1}} \Bigl( An-1 \Bigr)\Bigr) \Bigr) \Bigr)

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

… + \frac{C_{k-1}}{D_k} \Bigl( Ak\frac{C_k}{D_{k+1}} \Bigl( Ak+1\frac{C_{k+1}}{D_{k+2}} \Bigl( Ak+2 + …
… + \frac{C_{k-1}}{D_k} \Bigl( Ak\frac{C_k}{D_{k+1}} Ak+1\frac{C_k}{D_{k+1}} \frac{C_{k+1}}{D_{k+2}} \Bigl( Ak+2 + …
… + \frac{C_{k-1}}{D_k} \Bigl( \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}} \Bigl( Ak+2 + …
… + \frac{C_{k-1}}{D_kD_{k+1}} \Bigl( (AkDk+1CkAk+1) + \frac{C_kC_{k+1}}{D_{k+2}} \Bigl( Ak+2 + …

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

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