section_path: Modern quest for more digits/Spigot algorithms
section_name: Spigot algorithms
paragraph_text: Spigot algorithms
  
  Two algorithms were discovered in 1995 that opened up new avenues of research into π. They are called spigot algorithms because, like water dripping from a spigot, they produce single digits of π that are not reused after they are calculated. This is in contrast to infinite series or iterative algorithms, which retain and use all intermediate digits until the final result is produced.
  
  Mathematicians Stan Wagon and Stanley Rabinowitz produced a simple spigot algorithm in 1995. Its speed is comparable to arctan algorithms, but not as fast as iterative algorithms.
  
  Another spigot algorithm, the BBP digit extraction algorithm, was discovered in 1995 by Simon Plouffe: π = ∑ k = 0 ∞ 1 16 k (4 8 k + 1 − 2 8 k + 4 − 1 8 k + 5 − 1 8 k + 6). {\displaystyle \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).}
  
  This formula, unlike others before it, can produce any individual hexadecimal digit of π without calculating all the preceding digits. 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 π 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.
  
  Between 1998 and 2000, the distributed computing project PiHex used Bellard's formula (a modification of the BBP algorithm) to compute the quadrillionth (10 th) bit of π, which turned out to be 0. In September 2010, a Yahoo! employee used the company's Hadoop application on one thousand computers over a 23-day period to compute 256 bits of π at the two-quadrillionth (2×10 th) bit, which also happens to be zero.
  
  In 2022, Plouffe found a base-10 algorithm for calculating digits of π.