Editing Pi (section)

=== Computer era and iterative algorithms ===

The development of computers in the mid-20th century again revolutionized the hunt for digits of {{pi}}. Mathematicians [[John Wrench]] and Levi Smith reached 1,120 digits in 1949 using a desk calculator.{{sfn|Arndt|Haenel|2006|p=205}} 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.{{sfn|Arndt|Haenel|2006|p=197}}<ref>{{cite journal |last=Reitwiesner |first=George |title=An ENIAC Determination of pi and e to 2000 Decimal Places |journal=Mathematical Tables and Other Aids to Computation |year=1950 |volume=4 |issue=29 |pages=11–15 |doi=10.2307/2002695 |jstor=2002695}}</ref> The record, always relying on an arctan series, was broken repeatedly (3089 digits in 1955,<ref>{{cite journal |first1=J. C. |last1=Nicholson |first2=J. |last2=Jeenel |journal=Math. Tabl. Aids. Comp. |volume=9 |number=52 |year=1955 |doi=10.2307/2002052 |jstor=2002052 |title=Some comments on a NORC Computation of π |pages=162–164}}</ref> 7,480 digits in 1957; 10,000 digits in 1958; 100,000 digits in 1961) until 1 million digits was reached in 1973.{{sfn|Arndt|Haenel|2006|p=197}}

Two additional developments around 1980 once again accelerated the ability to compute {{pi}}. First, the discovery of new [[iterative algorithm]]s for computing {{pi}}, which were much faster than the infinite series; and second, the invention of [[Multiplication algorithm#Fast multiplication algorithms for large inputs|fast multiplication algorithms]] that could multiply large numbers very rapidly.{{sfn|Arndt|Haenel|2006|pp=15–17}} Such algorithms are particularly important in modern {{pi}} computations because most of the computer's time is devoted to multiplication.{{sfn|Arndt|Haenel|2006|p=131}} They include the [[Karatsuba algorithm]], [[Toom–Cook multiplication]], and [[FFT multiplication#Fourier transform methods|Fourier transform-based methods]].{{sfn|Arndt|Haenel|2006|pp=132, 140}}
{{quote box|quote=
The [[Gauss–Legendre algorithm|Gauss–Legendre iterative algorithm]]:{{br}}Initialize
<math display=block>\textstyle a_0 = 1, \quad b_0 = \frac{1}{\sqrt 2}, \quad t_0 = \frac{1}{4}, \quad p_0 = 1.</math>
Iterate
<math display=block>\textstyle a_{n+1} = \frac{a_n+b_n}{2}, \quad \quad b_{n+1} = \sqrt{a_n b_n},</math>
<math display=block>\textstyle t_{n+1} = t_n - p_n (a_n-a_{n+1})^2, \quad \quad p_{n+1} = 2 p_n.</math>
Then an estimate for {{pi}} is given by
<math display=block>\textstyle \pi \approx \frac{(a_n + b_n)^2}{4 t_n}.</math>
|fontsize=90%|qalign=left}}
The iterative algorithms were independently published in 1975–1976 by physicist [[Eugene Salamin (mathematician)|Eugene Salamin]] and scientist [[Richard Brent (scientist)|Richard Brent]].{{sfn|Arndt|Haenel|2006|p=87}} 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 [[AGM method|arithmetic–geometric mean method]] (AGM method) or [[Gauss–Legendre algorithm]].{{sfn|Arndt|Haenel|2006|p=87}} 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 [[Jonathan Borwein|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.<ref>{{harvnb|Arndt|Haenel|2006|p=111}} (5 times); pp. 113–114 (4 times). For details of algorithms, see {{cite book |last1=Borwein |first1=Jonathan |author-link1=Jonathan Borwein |last2=Borwein |first2=Peter |title=Pi and the AGM: a Study in Analytic Number Theory and Computational Complexity |publisher=Wiley |year=1987 |isbn=978-0-471-31515-5}}</ref> Iterative methods were used by Japanese mathematician [[Yasumasa Kanada]] to set several records for computing {{pi}} between 1995 and 2002.{{r|Background}} This rapid convergence comes at a price: the iterative algorithms require significantly more memory than infinite series.<ref name="Background">{{cite web |last=Bailey |first=David H. |author-link=David H. Bailey (mathematician) |url=http://crd-legacy.lbl.gov/~dhbailey/dhbpapers/dhb-kanada.pdf |title=Some Background on Kanada's Recent Pi Calculation |date=16 May 2003 |access-date=12 April 2012 |url-status=live |archive-url=https://web.archive.org/web/20120415102439/http://crd-legacy.lbl.gov/~dhbailey/dhbpapers/dhb-kanada.pdf |archive-date=15 April 2012}}</ref>