# 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 manygeneralized 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**: $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 byJohn 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 formula e.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

orGauss–Legendre algorithm **Salamin–Brent algorithm**was discovered independently by Richard Brent andEugene Salamin in1975 . 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"^{2}) algorithm is an improvement of the O("n"^{3}log("n")^{3}) 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"

^{3}log("n")^{3}) 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"^{2}). [*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 theUnited 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 functionarctan ("x"). This formula is most easily verified usingpolar coordinates ofcomplex number s, starting with:$(5+i)^4cdot(-239+i)=-114244-114244i.!$

Formulae of this kind are known as "

Machin-like formula e".Many other expressions for "π" were developed and published by Indian mathematician

Srinivasa Ramanujan . He worked with mathematicianGodfrey Harold Hardy in England for a number of years.Extremely long decimal expansions of "π" are typically computed with the

Gauss-Legendre algorithm andBorwein's algorithm ; theSalamin-Brent algorithm which was invented in1976 has also been used.The first one million digits of "π" and

^{1}/_{"π"}are available fromProject Gutenberg (see external links below).The record as of December2002 byYasumasa Kanada ofTokyo University stands at 1,241,100,000,000 digits, which were computed in September 2002 on a 64-node Hitachisupercomputer 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 andSimon Plouffe published a paper (Bailey, 1997) on a new formula for "π" as aninfinite 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 orhexadecimal 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 variousprogramming language s. ThePiHex project computed 64-bits around thequadrillion th 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*]

*Wikimedia Foundation.
2010.*

### Look at other dictionaries:

**computing**— com‧put‧ing [kəmˈpjuːtɪŋ] noun [uncountable] COMPUTING the activity of using a computer, or writing computer programs: • How are your computing skills? • She studied computing at college. • wireless mobile computing devices ˈgrid comˌputing … Financial and business terms**computing**— computing; su·per·computing; … English syllables**computing**— ► NOUN ▪ the use or operation of computers … English terms dictionary**Computing**— For the formal concept of computation, see computation. For the magazine, see Computing (magazine). For the scientific journal, see Computing (journal). A difference engine: computing the solution to a polynomial function … Wikipedia**computing**— noun 1. the procedure of calculating; determining something by mathematical or logical methods • Syn: ↑calculation, ↑computation • Derivationally related forms: ↑computational (for: ↑computation), ↑compute … Useful english dictionary**computing**— noun COMPUTING + NOUN ▪ skills ▪ power ▪ a hand held device that has as much computing power as many desktop PCs PREPOSITION ▪ in computing … Collocations dictionary**computing**— [[t]kəmpju͟ːtɪŋ[/t]] 1) N UNCOUNT Computing is the activity of using a computer and writing programs for it. Courses range from cookery to computing. 2) ADJ: ADJ n Computing means relating to computers and their use. Many graduates are employed… … English dictionary**computing**— /keuhm pyooh ting/, n. 1. the use of a computer to process data or perform calculations. 2. the act of calculating or reckoning. [1640 50; COMPUTE + ING1] * * * (as used in expressions) Reduced Instruction Set Computing DNA computing quantum… … Universalium**computing**— com|put|ing [kəmˈpju:tıŋ] n [U] the use of computers as a job, in a business etc ▪ Have you ever done any computing? ▪ computing facilities for language research … Dictionary of contemporary English**computing**— /kəmˈpjutɪŋ/ (say kuhm pyoohting) noun 1. the science or study of the principles and uses of computers. 2. the field of computer technology: to have a job in computing. –adjective 3. relating to computers: computing skills … Australian English dictionary