section_path: Modern quest for more digits/Computer era and iterative algorithms
section_name: Computer era and iterative algorithms
paragraph_text: Computer era and iterative algorithms
  
  The Gauss–Legendre iterative algorithm: Initialize a 0 = 1, b 0 = 1 2, t 0 = 1 4, p 0 = 1. {\displaystyle \textstyle a_{0}=1,\quad b_{0}={\frac {1}{\sqrt {2}}},\quad t_{0}={\frac {1}{4}},\quad p_{0}=1.} Iterate a n + 1 = a n + b n 2, b n + 1 = a n b n, {\displaystyle \textstyle a_{n+1}={\frac {a_{n}+b_{n}}{2}},\quad \quad b_{n+1}={\sqrt {a_{n}b_{n}}},} t n + 1 = t n − p n (a n − a n + 1) 2, p n + 1 = 2 p n. {\displaystyle \textstyle t_{n+1}=t_{n}-p_{n}(a_{n}-a_{n+1})^{2},\quad \quad p_{n+1}=2p_{n}.} Then an estimate for π is given by π ≈ (a n + b n) 2 4 t n. {\displaystyle \textstyle \pi \approx {\frac {(a_{n}+b_{n})^{2}}{4t_{n}}}.}
  
  The development of computers in the mid-20th century again revolutionized the hunt for digits of π. Mathematicians John Wrench and Levi Smith reached 1,120 digits in 1949 using a desk calculator. Using an inverse tangent (arctan) infinite series, a team led by George Reitwiesner and John von Neumann that same year achieved 2,037 digits with a calculation that took 70 hours of computer time on the ENIAC computer. The record, always relying on an arctan series, was broken repeatedly (3089 digits in 1955, 7,480 digits in 1957; 10,000 digits in 1958; 100,000 digits in 1961) until 1 million digits were reached in 1973.
  
  Two additional developments around 1980 once again accelerated the ability to compute π. First, the discovery of new iterative algorithms for computing π, which were much faster than the infinite series; and second, the invention of fast multiplication algorithms that could multiply large numbers very rapidly. Such algorithms are particularly important in modern π computations because most of the computer's time is devoted to multiplication. They include the Karatsuba algorithm, Toom–Cook multiplication, and Fourier transform-based methods.
  
  The iterative algorithms were independently published in 1975–1976 by physicist Eugene Salamin and scientist Richard Brent. These avoid reliance on infinite series. An iterative algorithm repeats a specific calculation, each iteration using the outputs from prior steps as its inputs, and produces a result in each step that converges to the desired value. The approach was actually invented over 160 years earlier by Carl Friedrich Gauss, in what is now termed the arithmetic–geometric mean method (AGM method) or Gauss–Legendre algorithm. As modified by Salamin and Brent, it is also referred to as the Brent–Salamin algorithm.
  
  The iterative algorithms were widely used after 1980 because they are faster than infinite series algorithms: whereas infinite series typically increase the number of correct digits additively in successive terms, iterative algorithms generally multiply the number of correct digits at each step. For example, the Brent–Salamin algorithm doubles the number of digits in each iteration. In 1984, brothers John and Peter Borwein produced an iterative algorithm that quadruples the number of digits in each step; and in 1987, one that increases the number of digits five times in each step. Iterative methods were used by Japanese mathematician Yasumasa Kanada to set several records for computing π between 1995 and 2002. This rapid convergence comes at a price: the iterative algorithms require significantly more memory than infinite series.