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

初期値の設定

${\displaystyle 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 回程度の反復でよい。

${\displaystyle {\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 を用いて以下のように近似される。

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

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

${\displaystyle 3.140\dots }$　（小数点以下2桁目までが正しい）

${\displaystyle 3.14159264\dots }$　（小数点以下7桁目までが正しい）

${\displaystyle 3.1415926535897932382\dots }$（小数点以下18桁目までが正しい）

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

Python3による実装例

#!/usr/bin/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())

算術幾何平均

二つの数${\displaystyle a_{0},b_{0}}$の算術幾何平均とは、数列

${\displaystyle a_{n+1}={\frac {a_{n}+b_{n}}{2}},\ b_{n+1}={\sqrt {a_{n}b_{n}}}}$

の極限のことである。両数列は同一の極限値を持つ。

${\displaystyle a_{0}=1,\ b_{0}=\cos \varphi }$のとき、算術幾何平均は${\displaystyle {\frac {\pi }{2K(\sin \varphi )}}}$となる。ここで、${\displaystyle K(k)}$は第一種完全楕円積分である。また、${\displaystyle c_{0}=\sin \varphi }$かつ${\displaystyle c_{i+1}=a_{i}-a_{i+1}}$なる数列について、

${\displaystyle \sum _{i=0}^{\infty }2^{i-1}{c_{i}}^{2}=1-{\frac {E(\sin \varphi )}{K(\sin \varphi )}}}$

が成立する。ここで、${\displaystyle E(k)}$は第二種完全楕円積分である。

ガウスはこれらの結果を知っていたとされる^[2][3][4]。

ルジャンドル恒等式

${\displaystyle \varphi +\theta ={\frac {\pi }{2}}}$なる${\displaystyle \varphi ,\theta }$について、ルジャンドルは次の恒等式を得た。

${\displaystyle K(\sin \varphi )E(\sin \theta )+K(\sin \theta )E(\sin \varphi )-K(\sin \varphi )K(\sin \theta )={\frac {\pi }{2}}.}$

この式は、任意の${\displaystyle \varphi }$について、以下のようにも書き表すことができる。

${\displaystyle K(\sin \varphi )\left\{E(\cos \varphi )-K(\cos \varphi )\right\}+K(\cos \varphi )E(\sin \varphi )={\frac {\pi }{2}}.}$

初等的な証明

ガウス＝ルジャンドルのアルゴリズムは楕円モジュラー関数を用いずに示すこともできる。初等的な積分を用いた証明が Lord (1992)^[5]、Milla (2019)^[6] によりなされている。