高斯-勒让德算法是一种用于计算圆周率（π）的算法。它以迅速收敛著称，只需25次迭代即可产生π的4500万位正确数字。不过，它的缺点是内存密集，因此有时它不如梅钦类公式使用广泛。

该方法基于德國數學家卡尔·弗里德里希·高斯（，1777–1855）和法國數學家阿德里安-马里·勒让德（，1752–1833）的个人成果与乘法和平方根运算之现代算法的结合。该算法反复替换两个数值的算术平均数和几何平均数，以接近它们的算术-几何平均数。

下文的版本也被称为高斯-欧拉，布伦特-萨拉明（或萨拉明-布伦特）算法；它于1975年被理查德·布伦特和尤金·萨拉明独立发现。日本筑波大学于2009年8月17日宣布利用此算法计算出π小数点后2,576,980,370,000位数字，计算结果用波温算法检验。

知名的电脑性能测试程序Super PI也使用此算法。

算法

设置初始值：

a_0 = 1\qquad b_0 = \frac{1}{\sqrt{2}}\qquad t_0 = \frac{1}{4}\qquad p_0 = 1.\!

反复执行以下步骤直到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}

则π的近似值为：

\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)\!为第二类完全椭圆积分：

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

高斯知道以上这两个结果。

勒让德恒等式
对于满足\varphi+\theta={1 \over 2}\pi\!的\varphi\!与\theta\!，勒让德证明了以下恒等式：
:K(\sin \varphi) E(\sin \theta ) + K(\sin \theta ) E(\sin \varphi) - K(\sin \varphi) K(\sin \theta) = {1 \over 2}\pi\!.

参考文献