AGM系
平均
$n$ 個の数値 $\{a_n\}$ の平均を取る場合、 その計算方法は何種類もあるが代表的なものとして次の 3 種類の平均の取り方を挙げる。
| 相加平均(算術平均) | 相乗平均(幾何平均) | 調和平均 |
|---|---|---|
| \[ M_A = \frac{1}{n}\sum_{k=1}^na_k \] | \[ M_G = \left(\prod_{k=1}^n a_k \right)^{1/n} \] | \[ M_H = \left(\frac{1}{n} \sum_{k=1}^n \frac{1}{a_k} \right)^{-1} \] |
2 数 $a$、$b$ に対して算術平均 (Arithmetic mean) と幾何平均 (Geometric mean) を繰り返し取ると共通の値に行きつく。 この値を算術幾何平均 (AGM ; Arithmetic and Geometric Mean) といい、 $M(a, b)$ で表す。
Gauß-Legendre の公式
数式表現
\[ a_0 = 1,\ b_0 = \frac{1}{\sqrt{2}} \] \[ a_{k+1} = \frac{1}{2} (a_k + b_k),\ b_{k+1} = \sqrt{a_kb_k} \]のとき、
\[ \pi = \frac{2 M(a_0, b_0)}{1-\sum_{k=0}^{\infty}2^k(a_k^2-b_k^2)} \]アルゴリズム表現
計算機で計算を行う場合、数式で表現されたままの計算を行うのは難しい。
1 つ 1 つの値が求めようとする $d$ 桁分の値を保持しなければならないため、 メモリや HDD といった記憶装置の使用領域を抑えるためには 同じ領域を使いまわさなければならない。 また、繰り返しを無限に行うことはできないので適切な回数処理を 繰り返したら処理を終えなければならない。 そのための実現アルゴリズムとして以下のようなものがある。 [JW06] ではより演算量を落としたアルゴリズムが提案されている。
- $A=1$
- $B=1/\sqrt{2}$
- $T=1/4$
- $x=1$
- $|A-B| \gt 10^{-d}$ の間、以下を繰り返す
- $Y=A$
- $A=(A+B)/2$
- $B=\sqrt{BY}$
- $T=T-x(Y-A)^2$
- $x=2x$
- $T = 4T$
- $\pi = (A+B)^2/T$