Gauss–Legendre algorithm

The Gauss–Legendre algorithm is an <a href="/facts/Algorithm/fnl5NmRt">algorithm</a> to compute the digits of <a href="/facts/Pi/vC0UBj1q">π</a>. 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 <a href="/facts/Random-access_memory/DuD4bxh6">computer memory</a>-intensive) and therefore all record-breaking calculations for many years have used other methods, almost always the <a href="/facts/Chudnovsky_algorithm/cQmCNhEn">Chudnovsky algorithm</a>. For details, see <a href="/facts/Chronology_of_computation_of_%25CF%2580/957BgxRP">Chronology of computation of π</a>.
The method is based on the individual work of <a href="/facts/Carl_Friedrich_Gauss/f4eSMBD7">Carl Friedrich Gauss</a> (1777–1855) and <a href="/facts/Adrien-Marie_Legendre/2a7CAolM">Adrien-Marie Legendre</a> (1752–1833) combined with modern algorithms for multiplication and <a href="/facts/Square_root/AfrzfBdQ">square roots</a>. It repeatedly replaces two numbers by their <a href="/facts/Arithmetic_mean/L3Pv333o">arithmetic</a> and <a href="/facts/Geometric_mean/6Nf6uk1A">geometric mean</a>, in order to approximate their <a href="/facts/Arithmetic-geometric_mean/8PRN9UB4">arithmetic-geometric mean</a>.
The version presented below is also known as the Gauss–Euler, Brent–Salamin (or Salamin–Brent) algorithm; it was independently discovered in 1975 by <a href="/facts/Richard_Brent_(scientist)/JYLmuA0M">Richard Brent</a> and <a href="/facts/Eugene_Salamin_(mathematician)/jU6R6gBJ">Eugene Salamin</a>. 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 <a href="/facts/Borwein%2527s_algorithm/MpPBybAo">Borwein's algorithm</a>.

Gauss–Legendre algorithm open-in-new

Gauss–Legendre algorithm