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

テンプレート:出典の明記 ガウス＝ルジャンドルのアルゴリズム（テンプレート:Lang-en）は、円周率を計算する際に用いられる数学の反復計算アルゴリズムである。円周率を計算するものの中では非常に収束が速く、2009年にこの式を用いてテンプレート:Math桁（約テンプレート:Math兆テンプレート:Math億桁）の計算がなされた。

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

アルゴリズム

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

初期値の設定

$a_0=1b_0=\frac{1}{\sqrt{2}}{t}_0=\frac{1}{4}{p}_0=1$

反復式

テンプレート:Math が希望する精度（桁数）になるまで以下の計算を繰り返す。小数第テンプレート:Math位まで求めるとき　テンプレート:Math 回程度の反復でよい。

$\begin{array}{cc}{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{array}$

テンプレート:Π の算出

円周率 テンプレート:Π は、テンプレート:Math を用いて以下のように近似される。

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

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

$3.140\dots$　（小数点以下テンプレート:Math桁目までが正しい）

$3.14159264\dots$　（小数点以下テンプレート:Math桁目までが正しい）

$3.1415926535897932382\dots$（小数点以下テンプレート:Math桁目までが正しい）

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

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())

数学的背景

算術幾何平均

二つの数$a_0,b_0$の算術幾何平均とは、数列

$a_{n+1}=\frac{a_n+b_n}{2},b_{n+1}=\sqrt{a_n{b}_n}$

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

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

$\sum _{i=0}^{\mathrm{\infty }}{2}^{i-1}{c_i}^2=1-\frac{E(\sin \phi )}{K(\sin \phi )}$

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

ガウスはこれらの結果を知っていたとされる。

ルジャンドル恒等式

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

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

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

$K(\sin \phi )\{E(\cos \phi )-K(\cos \phi )\}+K(\cos \phi )E(\sin \phi )=\frac{\pi }{2}.$

初等的な証明

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

関連項目

• [[スーパーπ|スーパーテンプレート:Π]]