The Gauss–Legendre algorithm is an
algorithm
In mathematics and computer science, an algorithm () is a finite sequence of rigorous instructions, typically used to solve a class of specific problems or to perform a computation. Algorithms are used as specifications for performing ...
to compute the digits of
. It is notable for being rapidly convergent, with only 25 iterations producing 45 million correct digits of . However, it has some drawbacks (for example, it is
computer memory
In computing, memory is a device or system that is used to store information for immediate use in a computer or related computer hardware and digital electronic devices. The term ''memory'' is often synonymous with the term '' primary storage ...
-intensive) and therefore all record-breaking calculations for many years have used other methods, almost always the
Chudnovsky algorithm
The Chudnovsky algorithm is a fast method for calculating the digits of , based on Ramanujan’s formulae. It was published by the Chudnovsky brothers in 1988.
It was used in the world record calculations of 2.7 trillion digits of in December ...
. For details, see
Chronology of computation of .
The method is based on the individual work of
Carl Friedrich Gauss
Johann Carl Friedrich Gauss (; german: Gauß ; la, Carolus Fridericus Gauss; 30 April 177723 February 1855) was a German mathematician and physicist who made significant contributions to many fields in mathematics and science. Sometimes refe ...
(1777–1855) and
Adrien-Marie Legendre
Adrien-Marie Legendre (; ; 18 September 1752 – 9 January 1833) was a French mathematician who made numerous contributions to mathematics. Well-known and important concepts such as the Legendre polynomials and Legendre transformation are nam ...
(1752–1833) combined with modern algorithms for multiplication and
square root
In mathematics, a square root of a number is a number such that ; in other words, a number whose ''square'' (the result of multiplying the number by itself, or ⋅ ) is . For example, 4 and −4 are square roots of 16, because .
...
s. It repeatedly replaces two numbers by their
arithmetic
Arithmetic () is an elementary part of mathematics that consists of the study of the properties of the traditional operations on numbers—addition, subtraction, multiplication, division, exponentiation, and extraction of roots. In the 19th c ...
and
geometric mean
In mathematics, the geometric mean is a mean or average which indicates a central tendency of a set of numbers by using the product of their values (as opposed to the arithmetic mean which uses their sum). The geometric mean is defined as the ...
, in order to approximate their
arithmetic-geometric mean.
The version presented below is also known as the Gauss–Euler, Brent–Salamin (or Salamin–Brent) algorithm; it was independently discovered in 1975 by
Richard Brent and
Eugene Salamin. It was used to compute the first 206,158,430,000 decimal digits of on September 18 to 20, 1999, and the results were checked with
Borwein's algorithm In mathematics, Borwein's algorithm is an algorithm devised by Jonathan and Peter Borwein to calculate the value of . They devised several other algorithms. They published the book ''Pi and the AGM – A Study in Analytic Number Theory and Computa ...
.
Algorithm
# Initial value setting:
# Repeat the following instructions until the difference of
and
is within the desired accuracy:
# is then approximated as:
The first three iterations give (approximations given up to and including the first incorrect digit):
:
:
:
The algorithm has
quadratic convergence
In numerical analysis, the order of convergence and the rate of convergence of a convergent sequence are quantities that represent how quickly the sequence approaches its limit. A sequence (x_n) that converges to x^* is said to have ''order of co ...
, which essentially means that the number of correct digits doubles with each
iteration
Iteration is the repetition of a process in order to generate a (possibly unbounded) sequence of outcomes. Each repetition of the process is a single iteration, and the outcome of each iteration is then the starting point of the next iteration. ...
of the algorithm.
Mathematical background
Limits of the arithmetic–geometric mean
The
arithmetic–geometric mean of two numbers, a
0 and b
0, is found by calculating the limit of the sequences
:
which both converge to the same limit.
If
and
then the limit is
where
is the
complete elliptic integral of the first kind
In integral calculus, an elliptic integral is one of a number of related functions defined as the value of certain integrals, which were first studied by Giulio Fagnano and Leonhard Euler (). Their name originates from their originally arising in ...
:
If
,
, then
:
where
is the
complete elliptic integral of the second kind
In integral calculus, an elliptic integral is one of a number of related functions defined as the value of certain integrals, which were first studied by Giulio Fagnano and Leonhard Euler (). Their name originates from their originally arising ...
:
:
and
Gauss knew of both of these results.
[ Salamin, Eugene, ''Computation of pi'', Charles Stark Draper Laboratory ISS memo 74–19, 30 January 1974, Cambridge, Massachusetts]
Legendre’s identity
Legendre proved the following identity:
:
[
]
Elementary proof with integral calculus
The Gauss-Legendre algorithm can be proven to give results converging to π using only integral calculus. This is done here and here.
See also
* Numerical approximations of
References
{{DEFAULTSORT:Gauss-Legendre algorithm
Pi algorithms