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

ガウス=ルジャンドルのアルゴリズム英語: Gauss–Legendre algorithm)は、円周率を計算する際に用いられる数学の反復計算アルゴリズムである。円周率を計算するものの中では非常に収束が速く、2009年にこの式を用いて2,576,980,370,000桁(約26000億桁)の計算がなされた。

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

アルゴリズム

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

初期値の設定

反復式

ab が希望する精度(桁数)になるまで以下の計算を繰り返す。小数第n位まで求めるとき log2n 回程度の反復でよい。

π の算出

円周率 π は、abt を用いて以下のように近似される。

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

 (小数点以下2桁目までが正しい)
 (小数点以下7桁目までが正しい)
(小数点以下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())

数学的背景

算術幾何平均

二つの数算術幾何平均とは、数列

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

のとき、算術幾何平均はとなる。ここで、第一種完全楕円積分である。また、かつなる数列について、

が成立する。ここで、第二種完全楕円積分である。

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

ルジャンドル恒等式

なるについて、ルジャンドルは次の恒等式を得た。

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

初等的な証明

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

脚注

  1. ^ Brent, Richard P. (1976-01-01). Traub, J. F.. ed (英語). Analytic Computational Complexity. Academic Press. pp. 151–176. doi:10.1016/b978-0-12-697560-4.50014-9. ISBN 978-0-12-697560-4. http://www.sciencedirect.com/science/article/pii/B9780126975604500149 
  2. ^ Salamin, Eugene (1976-07). “Computation of π Using Arithmetic-Geometric Mean”. Mathematics of Computation 30 (135): 565. doi:10.2307/2005327. https://www.jstor.org/stable/2005327?origin=crossref. 
  3. ^ Salamin, Eugene, Computation of pi, Charles Stark Draper Laboratory ISS memo 74–19, 30 January 1974, Cambridge, Massachusetts
  4. ^ Lord, Nick (1992-07). “Recent Calculations of p: The Gauss-Salamin Algorithm”. The Mathematical Gazette 76 (476): 231. doi:10.2307/3619132. https://www.jstor.org/stable/3619132?origin=crossref. 
  5. ^ Milla, Lorenz (2019), Easy Proof of Three Recursive π-Algorithms, arXiv:1907.04110

関連項目