Computing Digits of $\pi$

Researchers at the Fachhochschule Graubünden in Switzerland have announced the latest record for the number of digits of $\pi$ that have been computed. They have computed roughly 62.8 trillion digits using a supercomputer.

The work was done at the Zentrum für Data Analytics, Visualization and Simulation (DAViS).  Prof. Dr. Heiko Rölke is the leader of DAViS.  Thomas Keller is the project leader overseeing the calculations.  The computation took 108 days and 9 hours on a supercomputer.  The new record was in the news this week.  The announcement from their institution is here (in German). Here is a short NPR (audio) story.  Popular Mechanics had a nice article, and contacted Keller about their methods, as well as about the meaning of the calculation.  A key element to the DAViS group’s computation is the Chudnovsky algorithm, which has been used by other teams computing digits of $\pi$.

There is a long tradition of computing digits of $\pi$.  There is even an MSC2020 class for the family of such computations:  11Y60 Evaluation of number-theoretic constants.  Long ago, such computations were done by hand.  Wikipedia has a nice page with the history of the computations, and some related facts.  Early mathematicians in Egypt, Babylon, and China had approximations for $\pi$, usually as fractions.  As a formalized system, continued fractions provide an accessible method for generating good rational approximations to irrational numbers, including $\pi$.  The first few convergents in the continued fraction for $\pi$ are $\frac{3}{1}$, $\frac{22}{7}$, $\frac{333}{106}$, $\frac{355}{113}$. The sequence A001203 in the OEIS is the continued fraction representation of $\pi$, in the standard continued fraction shorthand.   Once we switched to using the decimal system, the digits became the target.   Various mathematicians, some unknown, some known, some famous, worked on computations of the digits of $\pi$.  Now, of course, we rely on computers, but we still need good algorithms.

As a non-expert in this area, one result that I find particularly fascinating is

MR1415794
Bailey, David (1-NASA9); Borwein, Peter (3-SFR); Plouffe, Simon (3-SFR)
On the rapid computation of various polylogarithmic constants. (English summary)
Math. Comp. 66 (1997), no. 218, 903–913.
11Y60

which provides a way of skipping intermediate digits and computing the $N$th hexadecimal digit of $\pi$ – also for certain other number-theoretic constants.  $N$ can be as large as you want, as the authors demonstrate by computing the ten billionth hexadecimal digit of $\pi$.  

For the news stories, the journalists usually ask “What’s this good for?”  The obvious answer is the tautological answer, but they are looking for applications outside number theory and outside mathematics.  Inside mathematics, methods of computing digits of $\pi$ and other mathematical constants are connected with developments of independent areas of mathematics.  One example is the theory of continued fractions, mentioned earlier.  Some of the efficient formulas (or series) for computing $\pi$ and other number-theoretic constants have connections with modular forms.  The work of David Bailey, Peter Borwein, Simon Plouffe involves the evaluation of special polylogarithms.  Peter Borwein and Jonathan Borwein wrote a nice book about the connection between $\pi$ and the algebraic-geometric mean (AGM).

MR0877728
Borwein, Jonathan M. (3-DLHS); Borwein, Peter B. (3-DLHS)
Pi and the AGM.
A study in analytic number theory and computational complexity. Canadian Mathematical Society Series of Monographs and Advanced Texts. A Wiley-Interscience Publication. John Wiley & Sons, Inc., New York, 1987. xvi+414 pp. ISBN: 0-471-83138-7
11Y60 (68Q30)

Doing insanely advanced versions of standard computations is also a nice way to test your algorithms and your hardware.  Keller is quoted in the Popular Mechanics article saying, “For us, the record is a byproduct of tuning our system for future computation tasks.”  An older example of this idea was a somewhat unintentional test and wasn’t computing digits of $\pi$, but Thomas Nicely‘s computations of primes, twin primes, and the like led to the discovery of hardware flaws in an Intel Pentium chip design in 1994.

Some reviews from MathSciNet

MR1415794
Bailey, David (1-NASA9); Borwein, Peter (3-SFR); Plouffe, Simon (3-SFR)
On the rapid computation of various polylogarithmic constants. (English summary)
Math. Comp. 66 (1997), no. 218, 903–913.
11Y60

The authors give algorithms for the computation of the $n{\rm th}$ digit of certain transcendental constants in (essentially) linear time and logarithmic space. The complexity class considered is denoted by ${\rm SC}^*$, which means ${\rm space}=\log^{O(1)}(n)$ and ${\rm time}=O(n\log^{O(1)}(n))$. As a typical example, the authors show how to compute, say, just the billionth binary digit of $\log(2)$, using single precision, within a few hours.

The existence of such an algorithm, which appears to be quite surprising at first, is based on the following idea. Suppose a constant $C$ can be represented as $C=\sum_{k=0}^\infty1/(b^{ck}q(k))$, where $b\ge2$ and $c$ are positive integers, and $q$ is a polynomial with integer coefficients $(q(k)\ne0)$. The task is to compute the $n{\rm th}$ digit of $C$ in base $b$. First observe that it is sufficient to compute $b^nC$ modulo 1. Clearly,
$$
b^nC\bmod1=\sum_{k=0}^\infty\frac{b^{n-ck}}{q(k)}\bmod1= \
\sum_{k=0}^{[n/c]}\frac{b^{n-ck}\bmod q(k)}{q(k)}\bmod1+\sum_{k=1+[n/c]}^\infty\frac{b^{n-ck}}{q(k)} \bmod1.
$$
In each term of the first sum, $b^{n-ck}\bmod q(k)$ is computed using the well-known fast exponentiation algorithm modulo the integer $q(k)$. Division by $q(k)$ and summation are performed using ordinary floating-point arithmetic. Concerning the infinite sum, note that the exponent in the numerator is negative. Thus, floating-point arithmetic can again be used to compute its value with sufficient accuracy. The final result, a fraction between 0 and 1, is then converted to the desired base $b$. With certain minor modifications, this scheme can be extended to numbers of the form $C=\sum_{k=0}^\infty p(k)/(b^{ck}q(k))$, where $p$ is a polynomial with integer coefficients.

It now happens that a large number of interesting transcendentals are of the form described. Many of the formulas depend on various polylogarithmic identities. Thus, define the $m{\rm th}$ polylogarithm $L_m$ by $L_m(z)=\sum_{j=1}^\infty z^j/j^m,\ |z|<1$. Then, for example, $-\log(1-2^{-n})=L_1(1/2^n)$, or $\pi^2=36L_2(\frac12)-36L_2(\frac14)-12L_2(\frac18)+6L_2(\frac1{64})$. One of the most striking identities is, however,$$\pi=\sum_{j=0}^\infty\frac1{16^j} \bigg(\frac4{8j+1}-\frac2{8j+4}-\frac1{8j+5}-\frac1{8j+6}\bigg).$$Using these formulas, it is easily shown that $-\log(1-2^{-n}),\ \pi$ or $\pi^2$ are in ${\rm SC}^*$. The authors demonstrate their technique by computing the ten billionth hexadecimal digit of $\pi,$ as well as the billionth hexadecimal digit of $\pi^2$ and $\log(2)$.

Reviewed by Andreas Guthmann

MR0877728
Borwein, Jonathan M. (3-DLHS); Borwein, Peter B. (3-DLHS)
Pi and the AGM.
A study in analytic number theory and computational complexity. Canadian Mathematical Society Series of Monographs and Advanced Texts. A Wiley-Interscience Publication. John Wiley & Sons, Inc., New York, 1987. xvi+414 pp. ISBN: 0-471-83138-7
11Y60 (68Q30)

This book reveals the close relationship between the algebraic-geometric mean iteration and the calculation of $\pi$.

The topic of algebraic-geometric mean iteration leads to a discussion on the theory of elliptic integrals and functions, theta functions and modular functions. The calculation of $\pi$ leads into the area of calculating algebraic functions, elementary functions and constants plus the transcendence of $\pi$ and $e$. The calculation of $\pi$ advanced with a frenzy with the advent of modern computers. Briefly, in 1706 the first 100 digits of $\pi$ were calculated. By 1844 the first 205 digits were known. In 1947 the first 808 digits of $\pi$ were computed using a desk calculator.

Then the modern computer came on the scene. Now the known first digits changed rapidly, which Table A partially illustrates:

These figures reveal, and Table B shows, how much the speed of computing has increased in a very short time.

Reviewed by H. London

MR1021452
Chudnovsky, D. V. (1-CLMB); Chudnovsky, G. V. (1-CLMB)
The computation of classical constants.
Proc. Nat. Acad. Sci. U.S.A. 86 (1989), no. 21, 8178–8182.
11Y60 (11-04 11Y35 33A99)

In this very interesting paper the authors make a large number of valuable comments on mathematics and algorithmics in connection with their computation of $\pi$ up to one billion digits. They give a short history of the computation of $\pi$ and some remarks on the evaluation of values of the hypergeometric functions. They explain how the Legendre relations for elliptic curves with complex multiplication give rise to Ramanujan’s series which are now used to compute $\pi$. Finally, some remarks on computer implementations are made.

Reviewed by F. Beukers

MR1222488
Borwein, J. M. (3-WTRL-B); Borwein, P. B. (3-DLHS)
Class number three Ramanujan type series for $1/\pi$. (English summary)
Computational complex analysis.
J. Comput. Appl. Math. 46 (1993), no. 1-2, 281–290.
11Y60 (11R11)

S. Ramanujan [Quart. J. Math. 45 (1914), 350–372; Jbuch 45, 186] exhibited certain series which converge very rapidly to $1/\pi$, of the form $\sum_{n\geq 0}(-1)^n((A+nB)/C^{3(n+1/2)})((6n)!/(3n)!n!^3)$. It turns out that for each squarefree integer $d$, the numbers $A$, $B$, $C$ are determined by the field $\mathbf{Q}(\sqrt{-d})$, and are actually $h$th degree algebraic integers, where $h$ is the class number of the field. The Chudnovskys have used such a series (with $h(-427)=2$), which adds 25 digits per term, to compute $\pi$ to a record two billion digits. Herein, the Borweins continue their fraternistic rivalry with the Chudnovskys by finding an example with $h(-1555)=4$ which adds about 50 digits per term. However, they have to deal with a quartic rather than quadratic irrational.

They also explicitly give the series approximating $1/\pi$ corresponding to each imaginary quadratic field of class number $3$ (surprisingly though, they provide no reference to tell us how they know that they have the complete list).

{For the collection containing this paper see MR1222468.}

Reviewed by Andrew Granville