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

ガウス＝ルジャンドルのアルゴリズム（）は、円周率を計算する際に用いられる数学の反復計算アルゴリズムである。円周率を計算するものの中では非常に収束が速く、2009年にこの式を用いて桁（約兆億桁）の計算がなされた。
このアルゴリズムはカール・フリードリヒ・ガウスとアドリアン＝マリ・ルジャンドルがそれぞれ別個に研究したものである。これはつの数値の算術幾何平均を求めるために、それぞれの数値を算術平均（相加平均）と幾何平均（相乗平均）で置き換えていくものである。
アルゴリズム.
これによる円周率の計算方法は以下の通りである。
反復式.
 が希望する精度（桁数）になるまで以下の計算を繰り返す。小数第位まで求めるとき　 回程度の反復でよい。
の算出.
円周率 は、 を用いて以下のように近似される。
最初の3回の反復で得られる数値（最後の桁は真値とは異なる）は以下の通りである。
この計算過程は二次収束する。つまり反復のたびに正しい桁数が直前のもののほぼ倍になるのである。ガウス自身もこの式を用いて反復を回まで行って桁まで正しいことを確認したことが知られている。
Python3による実装例.
import sys
from decimal import *
def picalc():
 a = Decimal(1)
 b = Decimal(1) / Decimal(2).sqrt()
 t = Decimal(1) / Decimal(4)
 p = Decimal(1)
 r = Decimal(0)
 rn = Decimal(3)
 while r != rn:
 r = rn
 an = (a + b) / 2
 bn = (a * b).sqrt()
 tn = t - p * (a - an) * (a - an)
 pn = 2 * p
 rn = ((a + b) * (a + b)) / (4 * t)
 a = an
 b = bn
 t = tn
 p = pn
 return rn
if __name__ == "__main__":
 if len(sys.argv) < 2:
 getcontext().prec = 10000
 else:
 try:
 getcontext().prec = int(sys.argv[1])
 except:
 print("引数が不正です。桁数を数値で指定して下さい。")
 sys.exit(1)
 print(picalc())
数学的背景.
算術幾何平均.
二つの数formula_7の算術幾何平均とは、数列
の極限のことである。両数列は同一の極限値を持つ。
formula_9のとき、算術幾何平均はformula_10となる。ここで、formula_11は第一種完全楕円積分である。また、formula_12かつformula_13なる数列について、
が成立する。ここで、formula_15は第二種完全楕円積分である。
ガウスはこれらの結果を知っていたとされる。
ルジャンドル恒等式.
formula_16なるformula_17について、ルジャンドルは次の恒等式を得た。
この式は、任意のformula_19について、以下のようにも書き表すことができる。
初等的な証明.
ガウス＝ルジャンドルのアルゴリズムは楕円モジュラー関数を用いずに示すこともできる。初等的な積分を用いた証明が Lord (1992)、Milla (2019) によりなされている。