# 高斯-勒让德算法

## 算法

1. 设置初始值：
${\displaystyle a_{0}=1\qquad b_{0}={\frac {1}{\sqrt {2}}}\qquad t_{0}={\frac {1}{4}}\qquad p_{0}=1.\!}$
2. 反复执行以下步骤直到${\displaystyle a_{n}\!}$${\displaystyle b_{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}}}
3. 则π的近似值为：
${\displaystyle \pi \approx {\frac {(a_{n+1}+b_{n+1})^{2}}{4t_{n+1}}}.\!}$

${\displaystyle 3.140\dots \!}$
${\displaystyle 3.14159264\dots \!}$
${\displaystyle 3.1415926535897932382\dots \!}$

## 数学背景

### 算术-几何平均数的极限

a0和b0两个数的算术-几何平均数，是通过计算它们的序列极限得到的：

{\displaystyle {\begin{aligned}a_{n+1}&={\frac {a_{n}+b_{n}}{2}},\\b_{n+1}&={\sqrt {a_{n}b_{n}}},\end{aligned}}}

${\displaystyle a_{0}=1\!}$${\displaystyle b_{0}=\cos \varphi \!}$，则极限为${\displaystyle {\pi \over 2K(\sin \varphi )}\!}$，其中${\displaystyle K(k)\!}$第一类完全椭圆积分

${\displaystyle K(k)=\int _{0}^{\pi \over 2}{\frac {d\theta }{\sqrt {1-k^{2}\sin ^{2}\theta }}}.\!}$

${\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-{E(\sin \varphi ) \over K(\sin \varphi )}\!}$

${\displaystyle E(k)=\int _{0}^{\pi \over 2}{\sqrt {1-k^{2}\sin ^{2}\theta }}\,d\theta .\!}$

### 勒让德恒等式

${\displaystyle K(\sin \varphi )E(\sin \theta )+K(\sin \theta )E(\sin \varphi )-K(\sin \varphi )K(\sin \theta )={1 \over 2}\pi \!.}$[3]

### 高斯-欧拉法

${\displaystyle \varphi =\theta ={\pi \over 4}\!}$的值可以代入勒让德恒等式，且K、E的近似值可通过${\displaystyle a_{0}=1\!}$${\displaystyle b_{0}=\sin {\pi \over 4}={\frac {1}{\sqrt {2}}}\!}$的算术-几何平均数的序列项得到。[6]

## 参考文献

1. ^ Brent, Richard, Old and New Algorithms for pi, Letters to the Editor, Notices of the AMS 60(1), p. 7
2. ^ 円周率計算桁数世界記録樹立について
3. Brent, Richard, Traub, J F , 编, Multiple-precision zero-finding methods and the complexity of elementary function evaluation, Analytic Computational Complexity (New York: Academic Press), 1975: 151–176 [8 September 2007]
4. ^ Salamin, Eugene, Computation of pi, Charles Stark Draper Laboratory ISS memo 74–19, 30 January, 1974, Cambridge, Massachusetts
5. ^ Salamin, Eugene, Computation of pi Using Arithmetic-Geometric Mean, Mathematics of Computation 30 (135), 1976, 30 (135): 565–570, ISSN 0025-5718
6. ^ Adlaj, Semjon, An eloquent formula for the perimeter of an ellipse, Notices of the AMS 59(8), p. 1096