高斯-勒让德算法
用於計算圓周率的演算法
(重定向自薩拉明 - 布倫特公式)
高斯-勒让德算法是一种用于计算圆周率(π)的算法。它以迅速收敛著称,只需25次迭代即可产生π的4500万位正确数字。不过,它的缺点是内存密集,因此有时它不如梅钦类公式使用广泛。
该方法基于德國數學家卡尔·弗里德里希·高斯(Johann Carl Friedrich Gauß,1777–1855)和法國數學家阿德里安-马里·勒让德(Adrien-Marie Legendre,1752–1833)的个人成果与乘法和平方根运算之现代算法的结合。该算法反复替换两个数值的算术平均数和几何平均数,以接近它们的算术-几何平均数。
下文的版本也被称为高斯-欧拉,布伦特-萨拉明(或萨拉明-布伦特)算法[1];它于1975年被理查德·布伦特和尤金·萨拉明独立发现。日本筑波大学于2009年8月17日宣布利用此算法计算出π小数点后2,576,980,370,000位数字,计算结果用波温算法检验。[2]
知名的电脑性能测试程序Super PI也使用此算法。
算法
- 设置初始值:
- 反复执行以下步骤直到 与 之间的误差到达所需精度:
- 则π的近似值为:
下面给出前三个迭代结果(近似值精确到第一个错误的位数):
该算法具有二阶收敛性,本质上说就是算法每执行一步正确位数就会加倍。
数学背景
算术-几何平均数的极限
a0和b0两个数的算术-几何平均数,是通过计算它们的序列极限得到的:
两者汇聚于同一极限。
若 且 ,则极限为 ,其中 为第一类完全椭圆积分:
若 , ,则
其中 为第二类完全椭圆积分:
勒让德恒等式
对于满足 的 与 ,勒让德证明了以下恒等式:
高斯-欧拉法
的值可以代入勒让德恒等式,且K、E的近似值可通过 与 的算术-几何平均数的序列项得到。[6]
参考文献
- ^ Brent, Richard, Old and New Algorithms for pi, Letters to the Editor, Notices of the AMS 60(1), p. 7
- ^ [円周率計算桁数世界記録樹立について (PDF). [2009-11-29]. (原始内容存档 (PDF)于2020-09-25). 円周率計算桁数世界記録樹立について]
- ^ 3.0 3.1 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], (原始内容存档于2008-07-23)
- ^ Salamin, Eugene, Computation of pi, Charles Stark Draper Laboratory ISS memo 74–19, 30 January, 1974, Cambridge, Massachusetts
- ^ Salamin, Eugene, Computation of pi Using Arithmetic-Geometric Mean, Mathematics of Computation 30 (135), 1976, 30 (135): 565–570, ISSN 0025-5718
- ^ Adlaj, Semjon, An eloquent formula for the perimeter of an ellipse, Notices of the AMS 59(8), p. 1096