- 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.
Besides its simple
continued fractionrepresentation [3; 7, 15, 1, 292, 1, 1, …] , which displays no discernible pattern, "π" has many generalized continued fractionrepresentations generated by a simple rule, including these two.
(Other representations are available at [http://functions.wolfram.com/Constants/Pi/10/ The Wolfram Functions Site] .)
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 , which leads to formulas where arises as the sum of small angles with rational tangents, such as these two by John Machin:
Formulas for "π" of this type are known as
Observing an equilateral triangle and noting that
The Salamin–Brent algorithm
Gauss–Legendre algorithmor Salamin–Brent algorithm was discovered independently by Richard Brent and Eugene Salaminin 1975. This can compute pi to N digits in time proportional to N log(N) log(log(N)), much faster than the trigonometric formulae.
Knowing that the formula can be simplified to get:
See: Double Factorial
Digit extraction methods
BBP formula (base 16)
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]
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"3log("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]
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"3log("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=
Fabrice Bellardimproved 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]
In the early years of the computer, the first expansion of "π" to 100,000 decimal places was computed by Maryland mathematician Dr.
Daniel Shanksand 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:
together with the
Taylor seriesexpansion of the function arctan("x"). This formula is most easily verified using polar coordinatesof complex numbers, starting with
Formulae of this kind are known as "
Many other expressions for "π" were developed and published by Indian mathematician
Srinivasa Ramanujan. He worked with mathematician Godfrey Harold Hardyin England for a number of years.
Extremely long decimal expansions of "π" are typically computed with the
Gauss-Legendre algorithmand Borwein's algorithm; the Salamin-Brent algorithmwhich was invented in 1976has also been used.
The first one million digits of "π" and 1/"π" are available from
Project Gutenberg(see external links below).The record as of December 2002by Yasumasa Kanadaof Tokyo Universitystands at 1,241,100,000,000 digits, which were computed in September 2002 on a 64-node Hitachi supercomputerwith 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:
::K. Takano (
: :F. C. W. Störmer (
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.)
1997, David H. Bailey, Peter Borweinand Simon Plouffepublished a paper (Bailey, 1997) on a new formula for "π" as an infinite series:
This formula permits one to fairly readily compute the "k"th binary or
hexadecimaldigit 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 PiHexproject computed 64-bits around the quadrillionth bit of "π" (which turns out to be 0). Fabrice Bellardclaims 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] :
Other formulæ that have been used to compute estimates of "π" include:
This converges extraordinarily rapidly. Ramanujan's work is the basis for the fastest algorithms used, as of the turn of the millennium, to calculate "π".
::David Chudnovsky and
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.
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.
History of numerical approximations of π
List of formulae involving π
Software for calculating π
Area of a disk
Liu Hui's π algorithm
* [http://mathworld.wolfram.com/PiFormulas.html Mathworld - Pi Formulas]
* [http://sourceforge.net/projects/projectpi/ Project Pi]
* [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