円周率.jp (http://xn--w6q13e505b.jp/formula/agm.html)

AGM系

平均

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

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 数 ab に対して算術平均 (Arithmetic mean) と幾何平均 (Geometric mean) を繰り返し取ると共通の値に行きつく. この値を算術幾何平均 (AGM ; Arithmetic Geometric Mean) といい, M(ab) で表す.

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 = $\frac{1}{\sqrt{2}}$
T = $\frac{1}{4}$
X = 1
while |AB|>10-d do
YA
A = $\frac{1}{2}$(AB)
B = $\\sqrt{BY}$
TTX(YA)2
X = 2X
end of while
$\pi = \frac{(A+B)^2}{4T}$