# 高斯-勒让德算法

## 算法

1. 设置初始值：
$a_0 = 1\qquad b_0 = \frac{1}{\sqrt{2}}\qquad t_0 = \frac{1}{4}\qquad p_0 = 1.\!$
2. 反复执行以下步骤直到$a_n\!$$b_n\!$之间的误差到达所需精度：
\begin{align} 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{align}
3. 则π的近似值为：
$\pi \approx \frac{(a_{n+1}+b_{n+1})^2}{4t_{n+1}}.\!$

$3.140\dots\!$
$3.14159264\dots\!$
$3.1415926535897932382\dots\!$

## 数学背景

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

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

\begin{align} a_{n+1} & = \frac{a_n+b_n}{2}, \\ b_{n+1} & = \sqrt{a_n b_n}, \end{align}

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

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

$c_0 = \sin\varphi\!$$c_{i+1} = a_i - a_{i+1}\!$，则

$\sum_{i=0}^\infty 2^{i-1} c_i^2 = 1 - {E(\sin\varphi)\over K(\sin\varphi)}\!$

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

### 勒让德恒等式

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

### 高斯-欧拉法

$\varphi=\theta={\pi\over 4}\!$的值可以代入勒让德恒等式，且K、E的近似值可通过$a_0=1\!$$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. ^ 3.0 3.1 Brent, Richard, Multiple-precision zero-finding methods and the complexity of elementary function evaluation, (编) Traub, J F, 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, 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