{
  "id": "enwiki-001355250971",
  "slug": "gauss-legendre-algorithm",
  "title": "Gauss–Legendre algorithm",
  "qid": "",
  "lead": "The Gauss–Legendre algorithm is an algorithm 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-intensive) and therefore all record-breaking calculations for many years have used other methods, almost always the Chudnovsky algorithm. For details, see Chronology of computation of . 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 roots. It repeatedly replaces two numbers by their arithmetic and geometric mean, 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 in 1999 to compute the first 200 billion decimal digits of , with results checked using Borwein's algorithm.",
  "body": "The Gauss–Legendre algorithm is an algorithm to compute the digits of . It is notable for being rapidly convergent, with only 25 iterations producing 45 million correct digits of&nbsp; . However, it has some drawbacks (for example, it is computer memory-intensive) and therefore all record-breaking calculations for many years have used other methods, almost always the Chudnovsky algorithm. For details, see Chronology of computation of . 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 roots. It repeatedly replaces two numbers by their arithmetic and geometric mean, 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 in 1999 to compute the first 200 billion decimal digits of , with results checked using Borwein's algorithm. Initial value setting: a_0 = 1\\qquad b_0 = \\frac{1}{\\sqrt{2}}\\qquad p_0 = 1\\qquad t_0 = \\frac{1}{4}. Repeat the following instructions until the difference between a_{n+1} and b_{n+1} is within the desired accuracy: \\begin{align} 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{align} is then approximated as: \\pi \\approx \\frac{(a_{n+1}+b_{n+1})^2}{4t_{n+1}}. The first five iterations give (approximations given up to and including the first incorrect digit): 3.140\\dots 3.14159264\\dots 3.1415926535897932382\\dots 3.14159265358979323846264338327950288419711\\dots 3.141592653589793238462643383279502884197169399375105820974944592307816406286208998625\\dots The algorithm has quadratic convergence, which essentially means that the number of correct digits doubles with each iteration of the algorithm. \\begin{align} a_{n+1} & = \\frac{a_n+b_n}{2}, \\\\[6pt] b_{n+1} & = \\sqrt{a_n b_n}, \\end{align} which both converge to the same limit. If a_0=1 and b_0=\\cos\\varphi then the limit is {\\pi \\over 2K(\\sin\\varphi)} where K(k) is the complete elliptic integral of the first kind K(k) = \\int_0^{\\pi/2} \\frac{d\\theta}{\\sqrt{1-k^2 \\sin^2\\theta}}. If c_0 = \\sin\\varphi , c_{i+1} = a_i - a_{i+1} , then \\sum_{i=0}^\\infty 2^{i-1} c_i^2 = 1 - {E(\\sin\\varphi)\\over K(\\sin\\varphi)} where E(k) is the complete elliptic integral of the second kind: E(k) = \\int_0^{\\pi/2}\\sqrt {1-k^2 \\sin^2\\theta}\\; d\\theta Gauss knew of these two results. K(\\cos \\theta) E(\\sin \\theta ) + K(\\sin \\theta ) E(\\cos \\theta) - K(\\cos \\theta) K(\\sin \\theta) = {\\pi \\over 2}, for all \\theta .",
  "categories": [
    "23118434",
    "23603337",
    "26709315"
  ],
  "license": "CC BY-SA 4.0",
  "source_uri": "https://en.wikipedia.org/w/index.php?oldid=1355250971",
  "content_hash": "",
  "created_at": null,
  "updated_at": 1779300254.0,
  "claims": [],
  "contradictions": [],
  "confidence": 0.6,
  "csl": {
    "id": "enwiki-001355250971",
    "type": "webpage",
    "title": "Gauss–Legendre algorithm",
    "author": [
      {
        "family": "Anticloud FZ LLE",
        "literal": "Anticloud FZ LLE"
      }
    ],
    "container-title": "encyclopegia.org",
    "publisher": "Anticloud FZ LLE",
    "publisher-place": "Dubai, United Arab Emirates",
    "URL": "https://encyclopegia.org/a/gauss-legendre-algorithm",
    "issued": {
      "date-parts": [
        [
          2026,
          11,
          21
        ]
      ]
    },
    "accessed": {
      "date-parts": [
        [
          2026,
          11,
          21
        ]
      ]
    },
    "license": "CC BY-SA 4.0",
    "DOI": "eo1:enwiki-001355250971",
    "isBasedOn": "https://en.wikipedia.org/w/index.php?oldid=1355250971",
    "note": "Immutable snapshot enwiki-001355250971"
  }
}