Computing π

Similarly, the more complex approximations of π given below involve repeated calculations of some sort, yielding closer and closer approximations with increasing numbers of calculations.

Continued fractions

Besides its simple continued fraction representation [3; 7, 15, 1, 292, 1, 1, …] , which displays no discernible pattern, "π" has many generalized continued fraction representations generated by a simple rule, including these two.

:$3+pi=\; \{6\; +\; cfrac\{1^2\}\{6\; +\; cfrac\{3^2\}\{6\; +\; cfrac\{5^2\}\{6\; +\; cfrac\{7^2\}\{ddots,\}!$

:$frac\{4\}\{pi\}\; =\; \{1\; +\; cfrac\{1^2\}\{3\; +\; cfrac\{2^2\}\{5\; +\; cfrac\{3^2\}\{7\; +\; cfrac\{4^2\}\{ddots\}!$

(Other representations are available at [http://functions.wolfram.com/Constants/Pi/10/ The Wolfram Functions Site] .)

Trigonometry

The Gregory-Leibniz series

: $frac\{pi\}\{4\}\; =\; frac\{1\}\{1\}\; -\; frac\{1\}\{3\}\; +\; frac\{1\}\{5\}\; -\; frac\{1\}\{7\}\; +\; cdots\; +\; frac\{(-1)^n\}\{2n+1\}\; +\; cdots!$

is the power series for arctan(x) specialized to "x" = 1. It converges too slowly to be of practical interest. However, the power series converges much faster for smaller values of $x$, which leads to formulas where $pi$ arises as the sum of small angles with rational tangents, such as these two by John Machin:

: $frac\{pi\}\{4\}\; =\; arctanfrac\{1\}\{2\}\; +\; arctanfrac\{1\}\{3\}!$

: $frac\{pi\}\{4\}\; =\; 4\; arctanfrac\{1\}\{5\}\; -\; arctanfrac\{1\}\{239\}!$

Formulas for "π" of this type are known as Machin-like formulae.

Observing an equilateral triangle and noting that

: $sinleft\; (frac\{pi\}\{6\}\; ight\; )=frac\{1\}\{2\}!$

yields

: $pi\; =\; 3\; sum\_\{n=0\}^infty\; \{2n\; choose\; n\}\; frac\{1\}\{(2n+1)\; 16^n\}\; =\; 3\; +\; frac\{1\}\{8\}\; +\; frac\{9\}\{640\}\; +\; frac\{15\}\{7168\}\; +\; cdots!$

The Salamin–Brent algorithm

The Gauss–Legendre algorithm or Salamin–Brent algorithm was discovered independently by Richard Brent and Eugene Salamin in 1975. This can compute pi to N digits in time proportional to N log(N) log(log(N)), much faster than the trigonometric formulae.

Arctangent

Knowing that $arctan(1)\; cdot\; 4\; =\; pi!$ the formula can be simplified to get:

: $cfrac\; \{pi\}\{2\}\; =\; sum\_\{n=0\}^\{infty\}\; cfrac\; \{n!\}\{(2n\; +\; 1)!!\}\; =\; 1\; +\; cfrac\{1\}\{3\}\; +\; cfrac\{1cdot2\}\{3cdot5\}\; +\; cfrac\{1cdot2cdot3\}\{3cdot5cdot7\}+cdots!$

See: Double Factorial

Digit extraction methods

BBP formula (base 16)

The Bailey–Borwein–Plouffe formula (BBP) for calculating pi was discovered in 1995 by Simon Plouffe. The formula computes pi in base 16 without needing to compute the previous digits (digit extraction). [MathWorld: BBP Formula http://mathworld.wolfram.com/BBPFormula.html]

: $pi=sum\_\{n=0\}^infty\; left(frac\{4\}\{8n+1\}-frac\{2\}\{8n+4\}-frac\{1\}\{8n+5\}-frac\{1\}\{8n+6\}\; ight)left(frac\{1\}\{16\}\; ight)^n!$

Bellard's improvement (base 2)

An alternative formula for computing pi in base 2 was derived by Fabrice Bellard. This O("n"²) algorithm is an improvement of the O("n"³log("n")³) algorithm, and has been measured to make computing binary digits of pi 43% faster. [Bellard's Website: http://fabrice.bellard.free.fr/pi/pi_bin/pi_bin.html]

: $pi=frac\{1\}\{2^6\}sum\_\{n=0\}^infty\; frac\{(-1)^n\}\{2^\{10n\; left\; (-frac\{2^5\}\{4n+1\}-frac\{1\}\{4n+3\}+frac\{2^8\}\{10n+1\}-frac\{2^6\}\{10n+3\}-frac\{2^2\}\{10n+5\}-frac\{2^2\}\{10n+7\}+frac\{1\}\{10n+9\}\; ight\; )!$

Extending to arbitrary bases

In 1996, Simon Plouffe derived an algorithm to extract the "n"th digit of pi in an arbitrary base in O("n"³log("n")³) time. [Simon Plouffe, "On the computation of the n'th decimal digit of various transcendental numbers", November 1996]

=Improvement using the Gosper formula=

In 1997, Fabrice Bellard improved Plouffe's formula for digit-extraction in an arbitrary base to reduce the runtime to O("n"²). [Bellard's Website: http://fabrice.bellard.free.fr/pi/pi_n2/pi_n2.html]

Efficient methods

In the early years of the computer, the first expansion of "π" to 100,000 decimal places was computed by Maryland mathematician Dr. Daniel Shanks and his team at the United States Naval Research Laboratory (N.R.L.) in 1961.

Daniel Shanks and his team used two different power series for calculating the digits of "π". For one it was known that any error would produce a value slightly high, and for the other, it was known that any error would produce a value slightly low. And hence, as long as the two series produced the same digits, there was a very high confidence that they were correct. The first 100,000 digits of "π" were published by the Naval Research Laboratory.

None of the formulæ given above can serve as an efficient way of approximating "π". For fast calculations, one may use a formula such as Machin's:

: $frac\{pi\}\{4\}\; =\; 4\; arctanfrac\{1\}\{5\}\; -\; arctanfrac\{1\}\{239\}!$

together with the Taylor series expansion of the function arctan("x"). This formula is most easily verified using polar coordinates of complex numbers, starting with

:$(5+i)^4cdot(-239+i)=-114244-114244i.!$

Formulae of this kind are known as "Machin-like formulae".

Many other expressions for "π" were developed and published by Indian mathematician Srinivasa Ramanujan. He worked with mathematician Godfrey Harold Hardy in England for a number of years.

Extremely long decimal expansions of "π" are typically computed with the Gauss-Legendre algorithm and Borwein's algorithm; the Salamin-Brent algorithm which was invented in 1976 has also been used.

The first one million digits of "π" and ¹/_"π" are available from Project Gutenberg (see external links below).The record as of December 2002 by Yasumasa Kanada of Tokyo University stands at 1,241,100,000,000 digits, which were computed in September 2002 on a 64-node Hitachi supercomputer with 1 terabyte of main memory, which carries out 2 trillion operations per second, nearly twice as many as the computer used for the previous record (206 billion digits). The following Machin-like formulæ were used for this:

:$frac\{pi\}\{4\}\; =\; 12\; arctanfrac\{1\}\{49\}\; +\; 32\; arctanfrac\{1\}\{57\}\; -\; 5\; arctanfrac\{1\}\{239\}\; +\; 12\; arctanfrac\{1\}\{110443\}!$:K. Takano (1982).

: $frac\{pi\}\{4\}\; =\; 44\; arctanfrac\{1\}\{57\}\; +\; 7\; arctanfrac\{1\}\{239\}\; -\; 12\; arctanfrac\{1\}\{682\}\; +\; 24\; arctanfrac\{1\}\{12943\}!$:F. C. W. Störmer (1896).

These approximations have so many digits that they are no longer of any practical use, except for testing new supercomputers. (Normality of "π" will always depend on the infinite string of digits on the end, not on any finite computation.)

In 1997, David H. Bailey, Peter Borwein and Simon Plouffe published a paper (Bailey, 1997) on a new formula for "π" as an infinite series:

: $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\}\; ight).!$

This formula permits one to fairly readily compute the "k"^th binary or hexadecimal digit of "π", withouthaving to compute the preceding "k" − 1 digits. [http://www.nersc.gov/~dhbailey/ Bailey's website] contains the derivation as well as implementations in various programming languages. The PiHex project computed 64-bits around the quadrillionth bit of "π" (which turns out to be 0).

Fabrice Bellard claims to have beaten the efficiency record set by Bailey, Borwein, and Plouffe with his formula to calculate binary digits of "π" [http://fabrice.bellard.free.fr/pi/pi_bin/pi_bin.html] :

:$pi\; =\; frac\{1\}\{2^6\}\; sum\_\{n=0\}^\{infty\}\; frac$(-1)}^n}{2^{10n left( - frac{2^5}{4n+1} - frac{1}{4n+3} + frac{2^8}{10n+1} - frac{2^6}{10n+3} - frac{2^2}{10n+5} - frac{2^2}{10n+7} + frac{1}{10n+9} ight)!

Other formulæ that have been used to compute estimates of "π" include:

:$frac\{pi\}\{2\}=sum\_\{k=0\}^inftyfrac\{k!\}\{(2k+1)!!\}=1+frac\{1\}\{3\}left(1+frac\{2\}\{5\}left(1+frac\{3\}\{7\}left(1+frac\{4\}\{9\}(1+cdots)\; ight)\; ight)\; ight)!$:Newton.

:$frac\{1\}\{pi\}\; =\; frac\{2sqrt\{2\{9801\}\; sum^infty\_\{k=0\}\; frac\{(4k)!(1103+26390k)\}\{(k!)^4\; 396^\{4k!$:Srinivasa Ramanujan.

This converges extraordinarily rapidly. Ramanujan's work is the basis for the fastest algorithms used, as of the turn of the millennium, to calculate "π".

:$frac\{1\}\{pi\}\; =\; 12\; sum^infty\_\{k=0\}\; frac\{(-1)^k\; (6k)!\; (13591409\; +\; 545140134k)\}\{(3k)!(k!)^3\; 640320^\{3k\; +\; 3/2!$:David Chudnovsky and Gregory Chudnovsky.

Projects

Pi Hex

Pi Hex was a project to compute three specific binary bits of π using a distributed network of several hundred computers. In 2000, after two years, the project finished computing the five trillionth, the forty trillionth, and the quadrillionth bits. All three of them turned out to be 0.

Background pi

Inspired by Pi Hex and Project Pi, [http://sourceforge.net/projects/backpi Background Pi] seeks to compute decimal digits of pi sequentially. The project has computed over a hundred thousand digits using spare CPU cycles. Background Pi is oriented to be more for an average end user than for a power user by offering an unobtrusive user interface. Research is underway on the efficiency of converting computed hex digits to decimal as computing hex digits is faster than computing decimal. A new version is in development that would manage multiple computation projects in a friendlier interface than BOINC.

ee also

* History of numerical approximations of π
* List of formulae involving π
* Software for calculating π
* Area of a disk
* Liu Hui's π algorithm

References

External links

General

* [http://mathworld.wolfram.com/PiFormulas.html Mathworld - Pi Formulas]

Computation

* [http://sourceforge.net/projects/projectpi/ Project Pi]

Distributed computation

* [http://sourceforge.net/projects/backpi Background Pi]