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

ガウス・ルジャンドル法は、円周率πの桁数を計算するアルゴリズムです。このアルゴリズムは収束が非常に速く、わずか25回の反復でπの4500万桁の正しい桁数を算出できることで知られています。しかし、いくつかの欠点（例えば、コンピュータのメモリを大量に消費する）があるため、長年にわたり、記録破りの計算には他の方法、ほぼ常にチュドノフスキー法が用いられてきました。詳細は、「πの計算の歴史」を参照してください。 

この方法は、カール・フリードリヒ・ガウス（1777～1855年）とアドリアン＝マリー・ルジャンドル（1752～1833年）の個々の研究に基づき、現代の乗算および平方根アルゴリズムを組み合わせたものです。2つの数をその算術平均と幾何平均で繰り返し置き換えることで、それらの算術平均と幾何平均を近似します。

以下に示すバージョンは、ガウス・オイラー、ブレント・サラミン（またはサラミン・ブレント）アルゴリズムとしても知られています。^{[ 1 ]}これは、1975 年にリチャード・ブレントとユージン・サラミンによって独立に発見されました。1999 年に、 πの最初の 2000 億桁を計算するために使用され、結果はボルウェインのアルゴリズムを使用して検証されました。

1. 初期値設定：$${\displaystyle a_{0}=1\qquad b_{0}={\frac {1}{\sqrt {2}}}\qquad p_{0}=1\qquad t_{0}={\frac {1}{4}}.}$$
2. 以下の手順を繰り返して、${\displaystyle a_{n+1}}$そして${\displaystyle b_{n+1}}$望ましい精度範囲内です。$${\displaystyle {\begin{aligned}a_{n+1}&={\frac {a_{n}+b_{n}}{2}},\\\\b_{n+1}&={\sqrt {a_{n}b_{n}}},\\\\p_{n+1}&=2p_{n},\\\\t_{n+1}&=t_{n}-p_{n}(a_{n+1}-a_{n})^{2}.\\\end{aligned}}}$$
3. πは次のように近似されます。$${\displaystyle \pi \approx {\frac {(a_{n+1}+b_{n+1})^{2}}{4t_{n+1}}}.}$$

最初の5回の反復計算では、（最初​​の誤った桁までの近似値として）次の値が得られます。

${\displaystyle 3.140\dots }$

${\displaystyle 3.14159264\dots }$

${\displaystyle 3.1415926535897932382\dots }$

${\displaystyle 3.14159265358979323846264338327950288419711\dots }$

${\displaystyle 3.141592653589793238462643383279502884197169399375105820974944592307816406286208998625\dots }$

このアルゴリズムは二次収束性を持ち、これは基本的に、アルゴリズムを繰り返すたびに正しい桁数が倍になることを意味します。

• πの数値近似