Pi Computation: History and Methods

Pi Computation History and Methods

Experiments Home

Mathematics

Pi Computation

Mathematics Science Fair Projects Home

Statistics & Probability

This page is a compilation of three articles:

Numerical Approximations of Pi

Computing Pi

Chronology of Computation of Pi

Numerical Approximations of Pi

Early history

An Egyptian scribe named Ahmes wrote the oldest known text to give an approximate value for π. The Rhind Mathematical Papyrus dates from the Egyptian Second Intermediate Period — though Ahmes stated that he copied a Middle Kingdom papyrus (i.e. from before 1650 BC) — and describes the value in such a way that the result obtained comes out to ²⁵⁶⁄₈₁, which is approximately 3.16, or 0.6% above the exact value.

As early as the 19th century BC, Babylonian mathematicians were using π ≈ ²⁵⁄₈, which is about 0.5% below the exact value.

The Indian astronomer Yajnavalkya gave astronomical calculations in the Shatapatha Brahmana (c. 9th century BC) that led to a fractional approximation of π ≈ ³³⁹⁄₁₀₈ (which equals 3.13888…, which is correct to two decimal places when rounded, or 0.09% below the exact value).

In the third century BC, Archimedes proved the sharp inequalities 3+¹⁰⁄₇₁ < π < 3+¹⁄₇, by means of regular 96-gons; these values are 0.02% and 0.04% off, repectively. (Differentiating the arctangent function leads to a simple modern proof that indeed 3+¹⁄₇ exceeds π.) Later, in the second century AD, Ptolemy using a regular 360-gon obtained a value of 3.141666... which is correct to three decimal places.

The Chinese mathematician Liu Hui in 263 AD computed π to 3.141014, which is correct to 3 decimal places (0.02% off), though he suggested that 3.14 was a good enough approximation.

Middle ages

Until 1000, π was known to fewer than 10 decimal digits only.

The Indian mathematician and astronomer Aryabhata in the 5th century gave an accurate approximation for π, and may have realized that π is irrational. He writes, in the second part of the Aryabhatiyam (gaṇitapāda 10):

chaturadhikam śatamaśṭaguṇam dvāśaśṭistathā sahasrāṇām
Ayutadvayaviśkambhasyāsanno vrîttapariṇahaḥ.

meaning "Add four to one hundred, multiply by eight and then add sixty-two thousand. The result is approximately the circumference of a circle of diameter twenty thousand. By this rule the relation of the circumference to diameter is given."

In other words (4+100)×8 + 62000 is the circumference of a circle with diameter 20000. This provides a value of π ≈ ⁶²⁸³²⁄₂₀₀₀₀ = 3.1416, correct to three decimal places. The commentator Nilakantha Somayaji, (Kerala School, 15th c.) has argued that the word āsanna (approaching), appearing just before the last word, here means not only that this is an approximation, but that the value is incommensurable (or irrational). If this is correct, it is quite a sophisticated insight, for the irrationality of pi was proved in Europe only in 1761 (Lambert). See Proof that π is irrational for an elementary 20th-century proof.

The Chinese mathematician and astronomer Zu Chongzhi in the 5th century computed π between 3.1415926 and 3.1415927, which was correct to 7 decimal places. He gave two other approximations of π: ³⁵⁵⁄₁₁₃ and ²²⁄₇.

In the 14th century, the Indian mathematician and astronomer Madhava of Sangamagrama gave two methods for computing the value of π. One of these methods is to obtain a rapidly converging series by transforming the original infinite series of π. By doing so, he obtained the infinite series

$\pi = \sqrt{12}\left(1-{1\over 3\cdot3}+{1\over5\cdot 3^2}-{1\over7\cdot 3^3}+\cdots\right)$

and used the first 21 terms to compute an approximation of π correct to 11 decimal places as 3.14159265359.

The other method he used was to add a remainder term to the original series of π. He used the remainder term

$\frac{n^2 + 1}{4n^3 + 5n}$

in the infinite series expansion of ^π⁄₄ to improve the approximation of π to 13 decimal places of accuracy when n = 75.

The Persian Muslim mathematician and astronomer Ghyath ad-din Jamshid Kashani (1380–1429) correctly computed 2π to 9 sexagesimal digits.^[1] This figure is equivalent to 16 decimal digits as

$\ 2\pi = 6.2831853071795865$

which equates to

$\ \pi = 3.14159265358979325.$

He achieved this level of accuracy by calculating the perimeter of a regular polygon with 3 × 2×10¹⁸ sides.

16th to 19th centuries

The German mathematician Ludolph van Ceulen (circa 1600) computed the first 32 decimal places of π. He was so proud of this accomplishment that he had them inscribed on his tombstone.

The Slovene mathematician Jurij Vega in 1789 calculated the first 140 decimal places for π of which the first 126 were correct [1] and held the world record for 52 years until 1841, when William Rutherford calculated 208 decimal places of which the first 152 were correct. Vega improved John Machin's formula from 1706 and his method is still mentioned today.

The English amateur mathematician William Shanks, a man of independent means, spent over 20 years calculating π to 707 decimal places (accomplished in 1873). His routine was as follows: he would calculate new digits all morning; and then he would spend all afternoon checking his morning's work. His work was made possible by the recent invention of the logarithm and its tables by Napier and Briggs. This was the longest expansion of π until the advent of the electronic digital computer a century later.

The Gauss-Legendre algorithm is used for calculating digits of π.

20th century

In 1910, the Indian mathematician Srinivasa Ramanujan found several rapidly converging infinite series of π, including

$\frac{1}{\pi} = \frac{2\sqrt{2}}{9801} \sum^\infty_{k=0} \frac{(4k)!(1103+26390k)}{(k!)^4 396^{4k}}$

which computes a further 8 decimal places of π with each term in the series. His series are now the basis for the fastest algorithms currently used to calculate π.

From the mid-20th century onwards, all calculations of π were done with the help of calculators or computers.

In 1944, D. F. Ferguson, with the aid of a mechanical desk calculator, found that William Shanks had made a mistake in the 528th decimal place, and that all succeeding digits were incorrect.

In the early years of the computer, the first expansion of π to 1,000,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 Washington, D.C. (Dr. Shanks's son Oliver Shanks, also a mathematician, states that there is no connection to William Shanks, and the family's roots are in Central Europe).

In 1961, Daniel Shanks and his team used two different power series for calculating the digital 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 N.R.L.^[2]

In 1989, the Chudnovsky brothers correctly computed π to over a billion decimal places on the supercomputer IBM 3090 using the following variation of Ramanujan's infinite series of π:

$\frac{1}{\pi} = 12 \sum^\infty_{k=0} \frac{(-1)^k (6k)! (13591409 + 545140134k)}{(3k)!(k!)^3 640320^{3k + 3/2}}.$

In 1999, Yasumasa Kanada and his team at the University of Tokyo correctly computed π to over 200 billion decimal places on the supercomputer HITACHI SR8000/MPP (128 nodes) using another variation of Ramanujan's infinite series of π. In October 2005 they claimed to have calculated it to 1.24 trillion places.^[3]

Less accurate approximations

Some approximations which have been given for π are notable in that they were less precise than previously known values.

Biblical value

It is sometimes claimed that the Bible states that π is 3, based on a passage in 1 Kings 7:23 (ca. 971-852 BCE) and 2 Chronicles 4:2 giving measurements for the round basin located in front of the Temple in Jerusalem as having a diameter of 10 cubits and a circumference of 30 cubits. Rabbi Nehemiah explained this in his Mishnat ha-Middot (the earliest known Hebrew text on geometry, ca. 150 CE) by saying that the diameter was measured from the outside of the brim while the circumference was measured along the inner rim. The stated dimensions would be exact if measured this way on a brim about four inches wide.

This is disputed, however, and other explanations have been offered, including that the measurements are given in round numbers (as the Hebrews tended to round off measurements to whole numbers), that cubits were not exact units, or that the basin may not have been exactly circular, or that the brim was wider than the bowl itself. Many reconstructions of the basin show a wider brim extending outward from the bowl itself by several inches. ^[4]

The Indiana bill

The "Indiana Pi Bill" of 1897, which never passed out of committee, has been claimed to imply a number of different values for π, although the closest it comes to explicitly asserting one is the wording "the ratio of the diameter and circumference is as five-fourths to four", which would make π = ¹⁶⁄₅ = 3.2.

Development of efficient formula

Machin-like formulae

For fast calculations, one may use formulæ such as Machin's:

$\frac{\pi}{4} = 4 \arctan\frac{1}{5} - \arctan\frac{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)^4\cdot(-239+i)=-114244-114244i.$

Another example is:

$\frac{\pi}{4} = \arctan\frac{1}{2} + \arctan\frac{1}{3}$

Formulæ of this kind are known as Machin-like formulae.

Other classical formulae

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

$\pi = \sqrt{12}\left(1-{1\over 3\cdot3}+{1\over5\cdot 3^2}-{1\over7\cdot 3^3}+\cdots\right)$

Madhava.

${\pi} = 20 \arctan\frac{1}{7} + 8 \arctan\frac{3}{79}$

Euler.

$\frac{\pi}{2}= \sum_{k=0}^\infty\frac{k!}{(2k+1)!!}= 1+\frac{1}{3}\left(1+\frac{2}{5}\left(1+\frac{3}{7}\left(1+\frac{4}{9}(1+\cdots)\right)\right)\right)$

Newton.

$\frac{1}{\pi} = \frac{2\sqrt{2}}{9801} \sum^\infty_{k=0} \frac{(4k)!(1103+26390k)}{(k!)^4 396^{4k}}$

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.

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

Modern algorithms

Extremely long decimal expansions of π are typically computed with iterative formulae like the Gauss-Legendre algorithm and Borwein's algorithm. The Salamin-Brent algorithm which was invented in 1976 is an example of the former.

Borwein's algorithm, found in 1985 by Jonathan and Peter Borwein, converges extremely fast: For $y_0=\sqrt2-1,\ a_0=6-4\sqrt2$ and

$y_{k+1}=(1-f(y_k))/(1+f(y_k)) ~,~ a_{k+1} = a_k(1+y_{k+1})^4 - 2^{2k+3} y_{k+1}(1+y_{k+1}+y_{k+1}^2)$

where $f (y) = (1 - y 4) 1 / 4$ , the sequence $1 / a k$ converges quartically to π, giving about 100 digits in three steps and over a trillion digits after 20 steps.

The first one million digits of π and ¹⁄_π are available from Project Gutenberg (see external links below). The current record (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 \arctan\frac{1}{49} + 32 \arctan\frac{1}{57} - 5 \arctan\frac{1}{239} + 12 \arctan\frac{1}{110443}$

K. Takano (1982).

$\frac{\pi}{4} = 44 \arctan\frac{1}{57} + 7 \arctan\frac{1}{239} - 12 \arctan\frac{1}{682} + 24 \arctan\frac{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.)

Formulae for binary digits

Main article: Bailey-Borwein-Plouffe formula

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

This formula permits one to easily compute the k^th binary or hexadecimal digit of π, without having to compute the preceding k − 1 digits. 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).

Miscellaneous formulæ

Historically, for a long time the base 60 was used for calculations. In this base, π can be approximated to eight (decimal!) significant figures as

$3 + \frac{8}{60} + \frac{29}{60^2} + \frac{44}{60^3}$

(The next sexagesimal digit is 0, causing truncation here to yield a relatively good approximation.)

In addition, the following expressions can be used to estimate π:

accurate to 9 digits:

$\frac{63}{25} \times \frac{17 + 15\sqrt{5}}{7 + 15\sqrt{5}}$

accurate to 9 places:

$\sqrt[4]{\frac{2143}{22}}$

This is from Ramanujan, who claimed the goddess Namagiri appeared to him in a dream and told him the true value of π.

accurate to 4 digits:

$\sqrt[3]{31}$

accurate to 3 digits:

$\sqrt{2} + \sqrt{3}$

Karl Popper conjectured that Plato knew this expression, that he believed it to be exactly π, and that this is responsible for some of Plato's confidence in the omnicompetence of mathematical geometry — and Plato's repeated discussion of special right triangles that are either isosceles or halves of equilateral triangles.

The continued fraction representation of π can be used to generate successive best rational approximations. These approximations are the best possible rational approximations of π relative to the size of their denominators. Here is a list of the first of these, punctuated at significant steps:

$\frac{3}{1},\quad \frac{13}{4},\frac{16}{5},\frac{19}{6},\frac{22}{7},\quad \frac{179}{57},\frac{201}{64}, \frac{223}{71},\frac{245}{78},\frac{267}{85},\frac{289}{92},\frac{311}{99},\frac{333}{106},\quad \frac{355}{113},\quad \frac{52163}{16604}$

Notes

^ Al-Kashi, author: Adolf P. Youschkevitch, chief editor: Boris A. Rosenfeld, p. 256
^ Shank, D. & Wrench, Jr., J. W. (1962), "Calculation of pi to 100,000 decimals", Mathematics of Computation 16: 76-99.
^ Announcement at the Kanada lab web site.
^ Math Forum - Ask Dr. Math

References

Bailey, David H., Borwein, Peter B., and Plouffe, Simon (April 1997). "On the Rapid Computation of Various Polylogarithmic Constants". Mathematics of Computation 66 (218): 903–913.
Joseph, George G. (2000). The Crest of the Peacock: Non-European Roots of Mathematics, New ed., London : Penguin. ISBN 0-14-027778-1.

Computing Pi

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} \le 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 $π$ .

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} \le 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)

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.

$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 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 $π$ 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 )=\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} + \ldots\!$

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{1\cdot2}{3\cdot5} + \cfrac{1\cdot2\cdot3}{3\cdot5\cdot7}+\ldots\!$

See: Double Factorial

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). ^[1]

$\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 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. ^[2]

$\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. ^[3]

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²). ^[4]

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 \arctan\frac{1}{5} - \arctan\frac{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)^4\cdot(-239+i)=-114244-114244i\!$ .

Formulæ 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 \arctan\frac{1}{49} + 32 \arctan\frac{1}{57} - 5 \arctan\frac{1}{239} + 12 \arctan\frac{1}{110443}\!$

K. Takano (1982).

$\frac{\pi}{4} = 44 \arctan\frac{1}{57} + 7 \arctan\frac{1}{239} - 12 \arctan\frac{1}{682} + 24 \arctan\frac{1}{12943}\!$

F. C. W. Störmer (1896).

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

This formula permits one to fairly readily compute the k^th binary or hexadecimal digit of π, without having to compute the preceding k − 1 digits. 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 π [1]:

$\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)\!$

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

$\frac{\pi}{2}=\sum_{k=0}^\infty\frac{k!}{(2k+1)!!}=1+\frac{1}{3}\left(1+\frac{2}{5}\left(1+\frac{3}{7}\left(1+\frac{4}{9}(1+\cdots)\right)\right)\right)\!$

Newton.

$\frac{1}{\pi} = \frac{2\sqrt{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, 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.

References

^ MathWorld: BBP Formula http://mathworld.wolfram.com/BBPFormula.html
^ Bellard's Website: http://fabrice.bellard.free.fr/pi/pi_bin/pi_bin.html
^ Simon Plouffe, On the computation of the n'th decimal digit of various transcendental numbers, November 1996
^ Bellard's Website: http://fabrice.bellard.free.fr/pi/pi_n2/pi_n2.html

External links

Chronology of Computation of π

The table below is a brief chronology of computed numerical values of, or bounds on, the mathematical constant π. See the history of numerical approximations of π for explanations, comments and details concerning some of the calculations mentioned below.

Date	Who	Value of π (world records in bold)
20th century BC	Egyptian Rhind Mathematical Papyrus	(16/9)² = 3.160493...
19th century BC	Babylonians	25/8 = 3.125
12th century BC	Chinese	3
9th century BC	Indian Shatapatha Brahmana	339/108 = 3.138888...
434 BC	Anaxagoras attempted to square the circle with compass and straightedge
c. 250 BC	Archimedes	223/71 < π < 22/7 (3.140845... < π < 3.142857...)
20 BC	Vitruvius	25/8 = 3.125
130	Chang Hong	√10 = 3.162277...
150	Ptolemy	377/120 = 3.141666...
250	Wang Fan	142/45 = 3.155555...
263	Liu Hui	3.141014
480	Zu Chongzhi	3.1415926 < π < 3.1415927
499	Aryabhata	62832/20000 = 3.1416
640	Brahmagupta	√10 = 3.162277...
800	Al Khwarizmi	3.1416
1150	Bhaskara	3.14156
1220	Fibonacci	3.141818
All records from 1400 onwards are given as the number of correct decimal places (dps).
1400	Madhava of Sangamagrama discovered the infinite power series expansion of π	11 dps 13 dps
1424	Jamshid Masud Al Kashi	16 dps
1573	Valenthus Otho	6 dps
1593	François Viète	9 dps
1593	Adriaen van Roomen	15 dps
1596	Ludolph van Ceulen	20 dps
1615	Ludolph van Ceulen	32 dps
1621	Willebrord Snell (Snellius), a pupil of Van Ceulen	35 dps
1665	Isaac Newton	16 dps
1699	Abraham Sharp	71 dps
1700	Seki Kowa	10 dps
1706	John Machin	100 dps
1706	William Jones introduced the Greek letter 'π'
1730	Kamata	25 dps
1719	Thomas Fantet de Lagny calculated 127 decimal places, but not all were correct	112 dps
1723	Takebe	41 dps
1739	Matsunaga Ryohitsu	50 dps
1748	Leonhard Euler used the Greek letter 'π' in his book Introductio in Analysin Infinitorum and assured its popularity.
1761	Johann Heinrich Lambert proved that π is irrational
1775	Euler pointed out the possibility that π might be transcendental
1794	Jurij Vega calculated 140 decimal places, but not all are correct	137 dps
1794	Adrien-Marie Legendre showed that π² (and hence π) is irrational, and mentioned the possibility that π might be transcendental.
1841	William Rutherford calculated 208 decimal places, but not all were correct	152 dps
1844	Zacharias Dase and Strassnitzky calculated 205 decimal places, but not all were correct	200 dps
1847	Thomas Clausen calculated 250 decimal places, but not all were correct	248 dps
1853	Lehmann	261 dps
1853	William Rutherford	440 dps
1855	Richter	500 dps
1874	William Shanks took 15 years to calculate 707 decimal places but not all were correct (the error was found by D. F. Ferguson in 1946)	527 dps
1882	Lindemann proved that π is transcendental (the Lindemann-Weierstrass theorem)
1897	The U.S. state of Indiana came close to legislating the value of 3.2 (among others) for π. House Bill No. 246 passed unanimously. The bill stalled in the state Senate due to a suggestion of possible commercial motives involving publication of a textbook. More detail can be found at http://www.cs.uu.nl/wais/html/na-dir/sci-math-faq/indianabill.html.
1910	Srinivasa Ramanujan finds several rapidly converging infinite series of π, which can compute 8 decimal places of π with each term in the series. Since the 1980s, his series have become the basis for the fastest algorithms currently used by Yasumasa Kanada and the Chudnovsky brothers to compute π.
1946	D. F. Ferguson (using a desk calculator)	620 dps
1947	Ivan Niven gave a very elementary proof that π is irrational
January 1947	D. F. Ferguson (using a desk calculator)	710 dps
September 1947	D. F. Ferguson (using a desk calculator)	808 dps
1949	D. F. Ferguson and John W. Wrench, using a desk calculator	1,120 dps
All records from 1949 onwards were calculated with electronic computers.
1949	John W. Wrench, Jr, and L. R. Smith were the first to use an electronic computer (the ENIAC) to calculate π (it took 70 hours) (also attributed to Reitwiesner et al)	2,037 dps
1953	Kurt Mahler showed that π is not a Liouville number
1954	S. C. Nicholson & J. Jeenel, using the NORC (it took 13 minutes)	3,092 dps
1957	G. E. Felton, using the Ferranti Pegasus computer (London)	7,480 dps
January 1958	Francois Genuys, using an IBM 704 (1.7 hours)	10,000 dps
May 1958	G. E. Felton, using the Pegasus computer (London) (33 hours)	10,020 dps
1959	Francois Genuys, using the IBM 704 (Paris) (4.3 hours)	16,167 dps
1961	IBM 7090 (London) (39 minutes)	20,000 dps
1961	Daniel Shanks and John W. Wrench, using the IBM 7090 (New York) (8.7 hours)	100,265 dps
1966	Jean Guilloud and J. Filliatre, using the IBM 7030 (Paris) (taking 28 hours??)	250,000 dps
1967	Jean Guilloud and M. Dichampt, using the CDC 6600 (Paris) (28 hours)	500,000 dps
1973	Jean Guilloud and M. Bouyer, using the CDC 7600	1,001,250 dps
1981	Yasumasa Kanada and Kazunori Miyoshi, FACOM M-200	2,000,036 dps
1981	Jean Guilloud, Not known	2,000,050 dps
1982	Yoshiaki Tamura, MELCOM 900II	2,097,144 dps
1982	Yasumasa Kanada, Yoshiaki Tamura, HITAC M-280H	4,194,288 dps
1982	Yasumasa Kanada, Yoshiaki Tamura, HITAC M-280H	8,388,576 dps
1983	Yasumasa Kanada, Yoshiaki Tamura, S. Yoshino, HITAC M-280H	16,777,206 dps
October 1983	Yasumasa Kanada and Yasunori Ushiro, HITAC S-810/20	10,013,395 dps
October 1985	William Gosper, Symbolics 3670	17,526,200 dps
January 1986	David H. Bailey, CRAY-2	29,360,111 dps
September 1986	Yasumasa Kanada, Yoshiaki Tamura, HITAC S-810/20	33,554,414 dps
October 1986	Yasumasa Kanada, Yoshiaki Tamura, HITAC S-810/20	67,108,839 dps
January 1987	Yasumasa Kanada, Yoshiaki Tamura, Yoshinobu Kubo, NEC SX-2	134,214,700 dps
January 1988	Yasumasa Kanada and Yoshiaki Tamura, HITAC S-820/80	201,326,551 dps
May 1989	Gregory V. Chudnovsky & David V. Chudnovsky, CRAY-2 & IBM 3090/VF	480,000,000 dps
June 1989	Gregory V. Chudnovsky & David V. Chudnovsky, IBM 3090	535,339,270 dps
July 1989	Yasumasa Kanada and Yoshiaki Tamura, HITAC S-820/80	536,870,898 dps
August 1989	Gregory V. Chudnovsky & David V. Chudnovsky, IBM 3090	1,011,196,691 dps
November 1989	Yasumasa Kanada and Yoshiaki Tamura, HITAC S-820/80	1,073,740,799 dps
August 1991	Gregory V. Chudnovsky & David V. Chudnovsky, Home made parallel computer (details unknown, not verified)	2,260,000,000 dps
May 1994	Gregory V. Chudnovsky & David V. Chudnovsky, New home made parallel computer (details unknown, not verified)	4,044,000,000 dps
June 1995	Yasumasa Kanada and Daisuke Takahashi (mathematician), HITAC S-3800/480 (dual CPU)	3,221,220,000 dps
August 1995	Yasumasa Kanada and Daisuke Takahashi (mathematician), HITAC S-3800/480 (dual CPU)	4,294,960,000 dps
September 1995	Yasumasa Kanada and Daisuke Takahashi (mathematician), HITAC S-3800/480 (dual CPU)	6,442,450,000 dps
June 1997	Yasumasa Kanada and Daisuke Takahashi (mathematician), HITACHI SR2201 (1024 CPU)	51,539,600,000 dps
April 1999	Yasumasa Kanada and Daisuke Takahashi (mathematician), HITACHI SR8000 (64 of 128 nodes)	68,719,470,000 dps
September 1999	Yasumasa Kanada and Daisuke Takahashi (mathematician), HITACHI SR8000/MPP (128 nodes)	206,158,430,000 dps
September 2002	Yasumasa Kanada & 9 man team, HITACHI SR8000/MPP (64 nodes), 600 hours	1,241,100,000,000 dps

External links

The Life of Pi by Jonathan Borwein

This article is licensed under the GNU Free Documentation License. It uses material from Wikipedia Encyclopedia article "Computing π"

My Dog Kelly

Site Map ♣ About Us ♣ Patent-Invent ♣ Free Theses, Dissertations & Patents
Comments and inquiries could be addressed to:
webmaster@julianTrubin.com

Contents

Early history

Middle ages

16th to 19th centuries

20th century

Less accurate approximations

Biblical value

The Indiana bill

Development of efficient formula

Machin-like formulae

Other classical formulae

Modern algorithms

Formulae for binary digits

Miscellaneous formulæ

See also

Notes

References

Contents

Standard methods

Circles

Continued fractions

Trigonometry

The Salamin-Brent algorithm

Arctangent

Digit extraction methods

BBP formula (base 16)

Bellard's improvement (base 2)

Extending to arbitrary bases

Improvement using the Gosper formula

Efficient methods

Projects

Pi Hex

Background pi

See also

References

External links

General

Computation

Distributed computation

See also

External links