Computing π

The following contains information regarding the computation of pi.

Standard methods

Circles

Pi can be obtained from a circle if its radius and area are known. Since the area of a circle is given by this formula:

$A=\pi r^{2}\,\!$

Elementary algebra allows solving for π:

$\pi =A/r^{2}.\,\!$

If a circle with radius r is drawn with its center at the point (0,0), any point whose distance from the origin is less than r will fall inside the circle. The Pythagorean theorem gives the distance from any point (x,y) to the center:

$d={\sqrt {x^{2}+y^{2}}}.$

Mathematical "graph paper" is formed by imagining a 1×1 square centered around each point (x,y), where x and y are integers between −r and r. Squares whose center resides inside or exactly on the border of the circle can then be counted by testing whether, for each point (x,y),

${\sqrt {x^{2}+y^{2}}}\leq r.$

The total number of points satisfying that condition thus approximates the area of the circle, which then can be used to calculate an approximation of $\pi$.

Mathematically, this formula can be written:

$\pi \approx {\frac {1}{r^{2}}}\sum _{x=-r}^{r}\;\sum _{y=-r}^{r}{\Big (}1{\hbox{ if }}{\sqrt {x^{2}+y^{2}}}\leq r,\;0{\hbox{ otherwise}}{\Big )}.$

In other words, begin by choosing a value for r. Consider all points (x,y) in which both x and y are integers between −r and r. Starting at 0, add 1 for each point whose distance to the origin (0,0) is less than or equal to r. When finished, divide the sum, representing the area of a circle of radius r, by r² to find the approximation of π. Closer approximations can be produced by using larger values of r.

For example, if r is 5, then the points considered are:

(−5,5)	(−4,5)	(−3,5)	(−2,5)	(−1,5)	(0,5)	(1,5)	(2,5)	(3,5)	(4,5)	(5,5)
(−5,4)	(−4,4)	(−3,4)	(−2,4)	(−1,4)	(0,4)	(1,4)	(2,4)	(3,4)	(4,4)	(5,4)
(−5,3)	(−4,3)	(−3,3)	(−2,3)	(−1,3)	(0,3)	(1,3)	(2,3)	(3,3)	(4,3)	(5,3)
(−5,2)	(−4,2)	(−3,2)	(−2,2)	(−1,2)	(0,2)	(1,2)	(2,2)	(3,2)	(4,2)	(5,2)
(−5,1)	(−4,1)	(−3,1)	(−2,1)	(−1,1)	(0,1)	(1,1)	(2,1)	(3,1)	(4,1)	(5,1)
(−5,0)	(−4,0)	(−3,0)	(−2,0)	(−1,0)	(0,0)	(1,0)	(2,0)	(3,0)	(4,0)	(5,0)
(−5,−1)	(−4,−1)	(−3,−1)	(−2,−1)	(−1,−1)	(0,−1)	(1,−1)	(2,−1)	(3,−1)	(4,−1)	(5,−1)
(−5,−2)	(−4,−2)	(−3,−2)	(−2,−2)	(−1,−2)	(0,−2)	(1,−2)	(2,−2)	(3,−2)	(4,−2)	(5,−2)
(−5,−3)	(−4,−3)	(−3,−3)	(−2,−3)	(−1,−3)	(0,−3)	(1,−3)	(2,−3)	(3,−3)	(4,−3)	(5,−3)
(−5,−4)	(−4,−4)	(−3,−4)	(−2,−4)	(−1,−4)	(0,−4)	(1,−4)	(2,−4)	(3,−4)	(4,−4)	(5,−4)
(−5,−5)	(−4,−5)	(−3,−5)	(−2,−5)	(−1,−5)	(0,−5)	(1,−5)	(2,−5)	(3,−5)	(4,−5)	(5,−5)

File:Kreuz-5.png

This circle as it would be drawn on a Cartesian coordinate graph. The points (±3,±4) and (±4,±3) are labelled.

The 12 points (0,±5), (±5,0), (±3,±4), (±4,±3) are exactly on the circle, and 69 points are completely inside, so the approximate area is 81, and π is calculated to be approximately 3.24 because 81 / 5² = 3.24. Results for some values of r are shown in the table below:

r	area	approximation of π
2	13	3.25
3	29	3.22222
4	49	3.0625
5	81	3.24
10	317	3.17
20	1257	3.1425
100	31417	3.1417
1000	3141549	3.141549

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.

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

$4/\pi ={1+{\cfrac {1^{2}}{3+{\cfrac {2^{2}}{5+{\cfrac {3^{2}}{7+{\cfrac {4^{2}}{\ddots }}}}}}}}}$

(Other representations are available at 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)^{i}}{2i+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}}=\arctan {\frac {1}{2}}+\arctan {\frac {1}{3}}$

${\frac {\pi }{4}}=4\arctan {\frac {1}{5}}-\arctan {\frac {1}{239}}$

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

Observing an equilateral triangle and noting that

$\sin \left({\frac {\pi }{6}}\right)=1/2$

yields

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

The Salamin-Brent algorithm

The 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.

Digit extraction methods

BBP formula (base 16)

The BBP(Bailey-Borwein-Plouffe) Formula 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).

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

Bellard's improvement (base 64)

An alternative formula for computing pi in base 64 was derived by Fabrice Bellard. This makes computing binary digits of pi 43% faster.

$\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}}\right)$

Extending to arbitrary bases

In 1996, Simon Plouffe derived an algorithm to calculate successive digits of pi in an arbitrary base in O(n³log(n)³) time.

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²).

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, 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.

See also

• History of numerical approximations of π
• List of formulae involving π
• Software for calculating π
• Area of a disk

External links

General

• Mathworld - Pi Formulas

Computation

• Project Pi

Distributed computation

• Background Pi