円周率.jp > 公式 > AGM系

AGM系

平均

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

3 種類の平均
相加平均(算術平均) 相乗平均(幾何平均) 調和平均
MA\frac{1}{n} \sum_{k=1}%5e{n}ak MG\Bigl(\prod_{k=1}%5e{n} ak\Bigr) 1/n MH\Bigl( \frac{1}{n} \sum_{k=1}%5e{n} ak-1 \Bigr)-1

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

Gauß-Legendre の公式

数式表現

a0 = 1, b0\frac{1}{\sqrt{2}}ak+1\frac{1}{2} (akbk), bk+1\sqrt{a_kb_k} のとき,
π = Gauß-Legendreの公式

アルゴリズム表現

計算機で計算を行う場合,数式で表現されたままの計算を行うのは難しい.

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
π = \frac{(A+B)%5e2}{4T}