AGM系

平均

$n$ 個の数値 $\{a_n\}$ の平均を取る場合、 その計算方法は何種類もあるが代表的なものとして次の 3 種類の平均の取り方を挙げる。

表 1: 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] ではより演算量を落としたアルゴリズムが提案されている。

  1. $A=1$
  2. $B=1/\sqrt{2}$
  3. $T=1/4$
  4. $x=1$
  5. $|A-B| \gt 10^{-d}$ の間、以下を繰り返す
    1. $Y=A$
    2. $A=(A+B)/2$
    3. $B=\sqrt{BY}$
    4. $T=T-x(Y-A)^2$
    5. $x=2x$
  6. $T = 4T$
  7. $\pi = (A+B)^2/T$