Editing Pi (section)

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