ガウス＝ルジャンドルのアルゴリズム

ガウス＝ルジャンドルのアルゴリズムは円周率を計算する際に用いられる数学の反復計算アルゴリズムである。円周率を計算するものの中では非常に収束が速く、2009年にこの式を用いて2,576,980,370,000桁（約2兆6000億桁）の計算がされた。

このアルゴリズムはカール・フリードリヒ・ガウスとアドリアン＝マリ・ルジャンドルがそれぞれ別個に研究したものである。これは2つの数値の算術幾何平均を求めるために、それぞれの数値を算術平均（相加平均）と幾何平均（相乗平均）で置き換えていくものである。

アルゴリズム[編集]

これによる円周率の計算方法は以下の通りである。

a_{0}=1\qquad b_{0}={\frac {1}{\sqrt {2}}}\qquad t_{0}={\frac {1}{4}}\qquad p_{0}=1

a, b が希望する精度（桁数）になるまで以下の計算を繰り返す。小数第n位まで求めるとき　log₂ n 回程度の反復でよい。

{\begin{aligned}a_{n+1}&={\frac {a_{n}+b_{n}}{2}}\\b_{n+1}&={\sqrt {a_{n}b_{n}}}\\t_{n+1}&=t_{n}-p_{n}(a_{n}-a_{n+1})^{2}\\p_{n+1}&=2p_{n}\end{aligned}}

円周率 $π$ は、a, b, t を用いて以下のように近似される。

\pi \approx {\frac {(a+b)^{2}}{4t}}

最初の3回の反復で得られる数値（最後の桁は真値とは異なる）は以下の通りである。

3.140\dots

　（小数点以下2桁目までが正しい）

3.14159264\dots

　（小数点以下7桁目までが正しい）

3.1415926535897932382\dots

（小数点以下18桁目までが正しい）

この計算過程は二次収束する。つまり反復のたびに正しい桁数が直前のもののほぼ2倍になるのである。ガウス自身もこの式を用いて反復を4回まで行って12桁まで正しいことを確認したことが知られている。