Gauss–Legendre algorithm: Difference between revisions

Revision as of 01:12, 26 February 2022

Latest revision as of 09:52, 15 June 2025

(19 intermediate revisions by 13 users not shown)

Line 1:

{{Short description|Quickly converging computation of π}}

The '''Gauss–Legendre algorithm''' is an [[algorithm]] to compute the digits of [[Pi|{{pi}}]]. It is notable for being rapidly convergent, with only 25 iterations producing 45 million correct digits of {{pi}}. However, theit drawbackhas issome thatdrawbacks (for example, it is [[Random-access_memory|computer memory]]-intensive) and therefore sometimesall record-breaking calculations for many years have used other methods, almost always the [[Machin-likeChudnovsky formulasalgorithm]]. areFor useddetails, insteadsee [[chronology of computation of π|Chronology of computation of {{pi}}]].

The method is based on the individual work of [[Carl Friedrich Gauss]] (1777–1855) and [[Adrien-Marie Legendre]] (1752–1833) combined with modern algorithms for multiplication and [[square root]]s. It repeatedly replaces two numbers by their [[arithmetic mean|arithmetic]] and [[geometric mean]], in order to approximate their [[arithmetic-geometric mean]].

Line 6 ⟶ 7:

== Algorithm ==

# Initial value setting: <math display="block">a_0 = 1\qquad b_0 = \frac{1}{\sqrt{2}}\qquad p_0 = 1\qquad t_0 = \frac{1}{4}\qquad p_0 = 1.</math>

# Repeat the following instructions until the difference ofbetween <math>a_na_{n+1}</math> and <math>b_nb_{n+1}</math> is within the desired accuracy: <math display="block"> \begin{align}

a_{n+1} & = \frac{a_n + b_n}{2}, \\

\\

b_{n+1} & = \sqrt{a_n b_n}, \\

\\

t_p_{n+1} & = t_n - p_n(a_{n}-a_{n+1})^22p_n, \\

\\

p_{n+1} & = 2p_n.

\\

t_{n+1} & = t_n - p_n(a_{n+1}-a_{n})^2. \\

\end{align}

</math>

Line 25:

:<math>3.14159264\dots</math>

:<math>3.1415926535897932382\dots</math>

:<math>3.14159265358979323846264338327950288419711\dots</math>

:<math>3.141592653589793238462643383279502884197169399375105820974944592307816406286208998625\dots</math>

The algorithm has [[quadratic convergence]], which essentially means that the number of correct digits doubles with each [[iteration]] of the algorithm.

Line 50 ⟶ 51:

where <math>E(k)</math> is the [[Elliptic integral#Complete elliptic integral of the second kind|complete elliptic integral of the second kind]]:

:<math>E(k) = \int_0^{\pi/2}\sqrt {1-k^2 \sin^2\theta}\; d\theta</math> and <math>K(k) = \int_0^{\pi/2}\frac{d\theta}{\sqrt {1-k^2 \sin^2\theta}}.</math>

Gauss knew of boththese of thesetwo results.<ref name="brent">{{Citation

| last=Brent

| first=Richard

Line 103 ⟶ 104:

| accessdate=

}}</ref>

=== Legendre’s identity ===

Legendre proved the following identity:

For <math>\varphi</math> and <math>\theta</math> such that <math display="inline">\varphi+\theta={1 \over 2}\pi</math> Legendre proved the identity:

:<math display="block">K(\sincos \varphitheta) E(\sin \theta ) + K(\sin \theta ) E(\sincos \varphitheta) - K(\sincos \varphitheta) K(\sin \theta) = {1\pi \over 2},</math>
for all <math>\pi.theta</math>.<ref name="brent" />

:Equivalently,

:<math>\forall \varphi: K(\sin\varphi)[E(\cos\varphi)-K(\cos\varphi)] + K(\cos\varphi)E(\sin\varphi) = \frac{\pi}{2}</math>

=== Elementary proof with integral calculus ===

The Gauss-Legendre algorithm can be proven to give results converging to <math>\pi</math> using only integral calculus. This is done here<ref>{{citation|title=Recent Calculations of π: The Gauss-Salamin Algorithm|last1=Lord|first1=Nick|doi=10.2307/3619132|year=1992|journal=The Mathematical Gazette|volume=76|issue=476|pages=231–242|jstor=3619132|s2cid=125865215 }}</ref> and here.<ref>{{citation|title=Easy Proof of Three Recursive π-Algorithms|last1=Milla|first1=Lorenz|arxiv=1907.04110|year=2019}}</ref>

== See also ==