Editing Pi (section)

== Modern quest for more digits ==

=== Motives for computing <span class="texhtml mvar" style="font-style:italic;">π</span> ===
[[File:Record pi approximations.svg|thumb|As mathematicians discovered new algorithms, and computers became available, the number of known decimal digits of {{pi}} increased dramatically. The vertical scale is [[logarithmic scale|logarithmic]].|upright=1.3]]
For most numerical calculations involving {{pi}}, a handful of digits provide sufficient precision. According to Jörg Arndt and Christoph Haenel, thirty-nine digits are sufficient to perform most [[cosmological]] calculations, because that is the accuracy necessary to calculate the circumference of the [[observable universe]] with a precision of one atom. Accounting for additional digits needed to compensate for computational [[round-off error]]s, Arndt concludes that a few hundred digits would suffice for any scientific application. Despite this, people have worked strenuously to compute {{pi}} to thousands and millions of digits.{{sfn|Arndt|Haenel|2006|pp=17–19}} This effort may be partly ascribed to the human compulsion to break records, and such achievements with {{pi}} often make headlines around the world.<ref>{{cite news |title=John W. Wrench, Jr.: Mathematician Had a Taste for Pi |first=Matt |last=Schudel |newspaper=The Washington Post |date=25 March 2009 |page=B5}} {{pb}} {{cite news |title=The Big Question: How close have we come to knowing the precise value of pi? |url=https://www.independent.co.uk/news/science/the-big-question-how-close-have-we-come-to-knowing-the-precise-value-of-pi-1861197.html |newspaper=The Independent |date=8 January 2010 |access-date=14 April 2012 |location=London |first=Steve |last=Connor |url-status=live |archive-url=https://web.archive.org/web/20120402220803/http://www.independent.co.uk/news/science/the-big-question-how-close-have-we-come-to-knowing-the-precise-value-of-pi-1861197.html |archive-date=2 April 2012}}</ref> They also have practical benefits, such as testing [[supercomputer]]s, testing numerical analysis algorithms (including [[Multiplication algorithm#Fast multiplication algorithms for large inputs|high-precision multiplication algorithms]]); and within pure mathematics itself, providing data for evaluating the randomness of the digits of {{pi}}.{{sfn|Arndt|Haenel|2006|pp=17-18}}<ref>{{cite journal |last1=Bailey |first1=David H. |author-link1=David H. Bailey (mathematician) |last2=Plouffe |first2=Simon M. |last3=Borwein |first3=Peter B. |last4=Borwein |first4=Jonathan M. |title=The quest for PI |journal=[[The Mathematical Intelligencer]] |volume=19 |issue=1 |year=1997 |pages=50–56 |issn=0343-6993 |doi=10.1007/BF03024340 |citeseerx=10.1.1.138.7085 |s2cid=14318695}}</ref>

=== 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>

=== Rapidly convergent series ===
[[File:Srinivasa Ramanujan - OPC - 2 (cleaned).jpg|thumb|upright=0.8|alt=Photo portrait of a man| [[Srinivasa Ramanujan]], working in isolation in India, produced many innovative series for computing {{pi}}.]]
Modern {{pi}} calculators do not use iterative algorithms exclusively. New infinite series were discovered in the 1980s and 1990s that are as fast as iterative algorithms, yet are simpler and less memory intensive.{{r|Background}} The fast iterative algorithms were anticipated in 1914, when Indian mathematician [[Srinivasa Ramanujan]] published dozens of innovative new formulae for {{pi}}, remarkable for their elegance, mathematical depth and rapid convergence.{{sfn|Arndt|Haenel|2006|pp=103–104}} One of his formulae, based on [[modular equation]]s, is

<math display=block>
\frac{1}{\pi} = \frac{2 \sqrt 2}{9801} \sum_{k=0}^\infty \frac{(4k)!(1103+26390k)}{k!^4\left(396^{4k}\right)}.
</math>

This series converges much more rapidly than most arctan series, including Machin's formula.{{sfn|Arndt|Haenel|2006|p=104}}[[Bill Gosper]] was the first to use it for advances in the calculation of {{pi}}, setting a record of 17 million digits in 1985.{{sfn|Arndt|Haenel|2006|pp=104, 206}} Ramanujan's formulae anticipated the modern algorithms developed by the Borwein brothers ([[Jonathan Borwein|Jonathan]] and [[Peter Borwein|Peter]]) and the [[Chudnovsky brothers]].{{sfn|Arndt|Haenel|2006|pp=110–111}} The [[Chudnovsky algorithm|Chudnovsky formula]] developed in 1987 is

<math display=block>
\frac{1}{\pi} = \frac{\sqrt{10005}}{4270934400} \sum_{k=0}^\infty \frac{(6k)! (13591409 + 545140134k)}{(3k)!\,k!^3 (-640320)^{3k}}.
</math>

It produces about 14 digits of {{pi}} per term{{sfn|Eymard|Lafon|2004|p=254}} and has been used for several record-setting {{pi}} calculations, including the first to surpass 1 billion (10<sup>9</sup>) digits in 1989 by the Chudnovsky brothers, 10 trillion (10<sup>13</sup>) digits in 2011 by Alexander Yee and Shigeru Kondo,<ref name="NW">{{cite book |last1=Bailey |first1=David H. |author1-link=David H. Bailey (mathematician) |last2=Borwein |first2=Jonathan M. |author2-link=Jonathan Borwein |contribution=15.2 Computational records |contribution-url=https://books.google.com/books?id=K26zDAAAQBAJ&pg=PA469 |doi=10.1007/978-3-319-32377-0 |page=469 |publisher=Springer International Publishing |title=Pi: The Next Generation, A Sourcebook on the Recent History of Pi and Its Computation |year=2016 |isbn=978-3-319-32375-6}}</ref> and 100 trillion digits by [[Emma Haruka Iwao]] in 2022.<ref>{{Cite magazine |url=https://thenewstack.io/how-googles-emma-haruka-iwao-helped-set-a-new-record-for-pi/ |title=How Google's Emma Haruka Iwao Helped Set a New Record for Pi |date=11 June 2022 |magazine=The New Stack |first=David |last=Cassel}}</ref><ref>{{Cite web |last=Haruka Iwao |first=Emma |author-link=Emma Haruka Iwao |url=https://cloud.google.com/blog/products/compute/calculating-31-4-trillion-digits-of-archimedes-constant-on-google-cloud |title=Pi in the sky: Calculating a record-breaking 31.4 trillion digits of Archimedes' constant on Google Cloud |website=[[Google Cloud Platform]] |date=14 March 2019 |access-date=12 April 2019 |archive-url=https://web.archive.org/web/20191019023120/https://cloud.google.com/blog/products/compute/calculating-31-4-trillion-digits-of-archimedes-constant-on-google-cloud |archive-date=19 October 2019 |url-status=live}}</ref>  For similar formulae, see also the [[Ramanujan–Sato series]].

In 2006, mathematician [[Simon Plouffe]] used the PSLQ [[integer relation algorithm]]<ref>PSLQ means Partial Sum of Least Squares.</ref> to generate several new formulae for {{pi}}, conforming to the following template:

<math display=block>
\pi^k = \sum_{n=1}^\infty \frac{1}{n^k} \left(\frac{a}{q^n-1} + \frac{b}{q^{2n}-1} + \frac{c}{q^{4n}-1}\right),
</math>

where {{math|''q''}} is {{math|[[Gelfond's constant|''e''<sup>''&pi;''</sup>]]}} (Gelfond's constant), {{math|''k''}} is an [[odd number]], and {{math|''a'', ''b'', ''c''}} are certain rational numbers that Plouffe computed.<ref>{{cite web |first=Simon |last=Plouffe |author-link=Simon Plouffe |title=Identities inspired by Ramanujan's Notebooks (part 2) |date=April 2006 |url=<!-- http://www.lacim.uqam.ca/~plouffe/inspired2.pdf -->http://plouffe.fr/simon/inspired2.pdf |access-date=10 April 2009 |url-status=live |archive-url=https://web.archive.org/web/20120114101641/http://www.plouffe.fr/simon/inspired2.pdf |archive-date=14 January 2012}}</ref>

=== Monte Carlo methods ===
{{multiple image
| direction         = horizontal
| image1            = Buffon needle.svg
| caption1          = [[Buffon's needle]]. Needles ''a'' and ''b'' are dropped randomly.
| alt1              = Needles of length ''ℓ'' scattered on stripes with width ''t''
| image2            = Pi 30K.gif
| caption2          = Random dots are placed on a square and a circle inscribed inside.
| alt2              = Thousands of dots randomly covering a square and a circle inscribed in the square.
| align             = left
| total_width       = 225
}}
[[Monte Carlo methods]], which evaluate the results of multiple random trials, can be used to create approximations of {{pi}}.{{sfn|Arndt|Haenel|2006|p=39}} [[Buffon's needle]] is one such technique: If a needle of length {{math|''ℓ''}} is dropped {{math|''n''}} times on a surface on which parallel lines are drawn {{math|''t''}} units apart, and if {{math|''x''}} of those times it comes to rest crossing a line ({{math|''x''}}&nbsp;>&nbsp;0), then one may approximate {{pi}} based on the counts:<ref name="bn">{{cite journal |last=Ramaley |first=J. F. |title=Buffon's Needle Problem |jstor=2317945 |journal=The American Mathematical Monthly |volume=76 |issue=8 |date=October 1969 |pages=916–918 |doi=10.2307/2317945}}</ref>

<math display=block>\pi \approx \frac{2n\ell}{xt}.</math>

Another Monte Carlo method for computing {{pi}} is to draw a circle inscribed in a square, and randomly place dots in the square. The ratio of dots inside the circle to the total number of dots will approximately equal {{math|π/4}}.<ref>{{harvnb|Arndt|Haenel|2006|pp=39–40}}.{{br}} {{harvnb|Posamentier|Lehmann|2004|p=105}}.</ref>

[[File:Five random walks.png|thumb|Five random walks with 200 steps.  The sample mean of {{math|{{abs|''W''<sub>200</sub>}}}} is {{math|''μ'' {{=}} 56/5}}, and so {{math|2(200)''μ''<sup>−2</sup> ≈ 3.19}} is within {{math|0.05}} of&nbsp;{{pi}}.|left]]
Another way to calculate {{pi}} using probability is to start with a [[random walk]], generated by a sequence of (fair) coin tosses: independent [[random variable]]s {{math|''X<sub>k</sub>''}} such that {{math|''X<sub>k</sub>'' ∈ {{mset|−1,1}}}} with equal probabilities.  The associated random walk is

<math display=block>W_n = \sum_{k=1}^n X_k</math>

so that, for each {{mvar|n}}, {{math|''W<sub>n</sub>''}} is drawn from a shifted and scaled [[binomial distribution]].  As {{mvar|n}} varies, {{math|''W<sub>n</sub>''}} defines a (discrete) [[stochastic process]].  Then {{pi}} can be calculated by<ref>{{cite journal |last=Grünbaum |first=B. |author-link=Branko Grünbaum |title=Projection Constants |journal=[[Transactions of the American Mathematical Society]] |volume=95 |issue=3 |pages=451–465 |year=1960 |doi=10.1090/s0002-9947-1960-0114110-9 |doi-access=free}}</ref>

<math display=block>\pi = \lim_{n\to\infty} \frac{2n}{E[|W_n|]^2}.</math>

This Monte Carlo method is independent of any relation to circles, and is a consequence of the [[central limit theorem]], discussed [[#Gaussian integrals|below]].

These Monte Carlo methods for approximating {{pi}} are very slow compared to other methods, and do not provide any information on the exact number of digits that are obtained. Thus they are never used to approximate {{pi}} when speed or accuracy is desired.<ref>{{harvnb|Arndt|Haenel|2006|p=43}}.{{br}}{{harvnb|Posamentier|Lehmann|2004|pp=105–108}}.</ref>

=== Spigot algorithms ===
Two algorithms were discovered in 1995 that opened up new avenues of research into {{pi}}. They are called [[spigot algorithm]]s because, like water dripping from a [[Tap (valve)|spigot]], they produce single digits of {{pi}} that are not reused after they are calculated.{{sfn|Arndt|Haenel|2006|pp=77–84}}<ref name="Gibbons">{{cite journal |last=Gibbons |first=Jeremy |author-link=Jeremy Gibbons |doi=10.2307/27641917 |issue=4 |journal=[[The American Mathematical Monthly]] |jstor=27641917 |mr=2211758 |pages=318–328 |title=Unbounded spigot algorithms for the digits of pi |url=https://www.cs.ox.ac.uk/jeremy.gibbons/publications/spigot.pdf |volume=113 |year=2006}}</ref> This is in contrast to infinite series or iterative algorithms, which retain and use all intermediate digits until the final result is produced.{{sfn|Arndt|Haenel|2006|pp=77–84}}

Mathematicians [[Stan Wagon]] and Stanley Rabinowitz produced a simple spigot algorithm in 1995.{{r|Gibbons}}{{sfn|Arndt|Haenel|2006|p=77}}<ref>{{cite journal |first1=Stanley |last1=Rabinowitz |last2=Wagon |first2=Stan |date=March 1995 |title=A spigot algorithm for the digits of Pi |journal=American Mathematical Monthly |volume=102 |issue=3 |pages=195–203 |doi=10.2307/2975006 |jstor=2975006}}</ref> Its speed is comparable to arctan algorithms, but not as fast as iterative algorithms.{{sfn|Arndt|Haenel|2006|p=77}}

Another spigot algorithm, the [[Bailey–Borwein–Plouffe formula|BBP]] [[digit extraction algorithm]], was discovered in 1995 by Simon Plouffe:{{sfn|Arndt|Haenel|2006|pp=117, 126–128}}<ref name="bbpf">{{cite journal |last1=Bailey |first1=David H. |author-link=David H. Bailey (mathematician) |last2=Borwein |first2=Peter B. |author2-link=Peter Borwein |last3=Plouffe |first3=Simon |author3-link=Simon Plouffe |date=April 1997 |title=On the Rapid Computation of Various Polylogarithmic Constants |journal=Mathematics of Computation |volume=66 |issue=218 |pages=903–913 |url=<!-- http://crd.lbl.gov/~dhbailey/dhbpapers/digits.pdf -->http://crd-legacy.lbl.gov/~dhbailey/dhbpapers/digits.pdf |doi=10.1090/S0025-5718-97-00856-9 |url-status=live |archive-url=https://web.archive.org/web/20120722015837/http://crd-legacy.lbl.gov/~dhbailey/dhbpapers/digits.pdf |archive-date=22 July 2012 |citeseerx=10.1.1.55.3762 |bibcode=1997MaCom..66..903B |s2cid=6109631}}</ref>
<math display=block> \pi = \sum_{k=0}^\infty \frac{1}{16^k} \left( \frac{4}{8k + 1} - \frac{2}{8k + 4} - \frac{1}{8k + 5} - \frac{1}{8k + 6}\right).</math>

This formula, unlike others before it, can produce any individual [[hexadecimal]] digit of {{pi}} without calculating all the preceding digits.{{sfn|Arndt|Haenel|2006|pp=117, 126–128}} Individual binary digits may be extracted from individual hexadecimal digits, and [[octal]] digits can be extracted from one or two hexadecimal digits. An important application of digit extraction algorithms is to validate new claims of record {{pi}} computations: After a new record is claimed, the decimal result is converted to hexadecimal, and then a digit extraction algorithm is used to calculate several randomly selected hexadecimal digits near the end; if they match, this provides a measure of confidence that the entire computation is correct.{{r|NW}}

Between 1998 and 2000, the [[distributed computing]] project [[PiHex]] used [[Bellard's formula]] (a modification of the BBP algorithm) to compute the quadrillionth (10<sup>15</sup>th) bit of {{pi}}, which turned out to be 0.<ref>{{harvnb|Arndt|Haenel|2006|p=20}}.{{br}} Bellards formula in: {{cite web |url=http://fabrice.bellard.free.fr/pi/pi_bin/pi_bin.html |title=A new formula to compute the n<sup>th</sup> binary digit of pi |first=Fabrice |last=Bellard |author-link=Fabrice Bellard |access-date=27 October 2007 |archive-url=https://web.archive.org/web/20070912084453/http://fabrice.bellard.free.fr/pi/pi_bin/pi_bin.html <!-- http://www.lacim.uqam.ca/~plouffe/inspired2.pdf --> |archive-date=12 September 2007}}</ref> In September 2010, a [[Yahoo!]] employee used the company's [[Apache Hadoop|Hadoop]] application on one thousand computers over a 23-day period to compute 256 [[bit]]s of {{pi}} at the two-quadrillionth (2×10<sup>15</sup>th) bit, which also happens to be zero.<ref>{{cite news |title=Pi record smashed as team finds two-quadrillionth digit |last=Palmer |first=Jason |newspaper=BBC News |date=16 September 2010 |url=https://www.bbc.co.uk/news/technology-11313194 |access-date=26 March 2011 |url-status=live |archive-url=https://web.archive.org/web/20110317170643/http://www.bbc.co.uk/news/technology-11313194 |archive-date=17 March 2011}}</ref>

In 2022, Plouffe found a base-10 algorithm for calculating digits of {{pi}}.<ref>{{cite arXiv |last=Plouffe |first=Simon |author-link=Simon Plouffe |year=2022 |eprint=2201.12601 |title=A formula for the {{mvar|n}}th decimal digit or binary of {{mvar|π}} and powers of {{mvar|π}} |class=math.NT}}</ref>