{"id":3238,"date":"2021-08-20T00:57:30","date_gmt":"2021-08-20T04:57:30","guid":{"rendered":"https:\/\/blogs.ams.org\/beyondreviews\/?p=3238"},"modified":"2021-08-20T00:57:30","modified_gmt":"2021-08-20T04:57:30","slug":"computing-digits-of-pi","status":"publish","type":"post","link":"https:\/\/blogs.ams.org\/beyondreviews\/2021\/08\/20\/computing-digits-of-pi\/","title":{"rendered":"Computing Digits of $\\pi$"},"content":{"rendered":"

\"AResearchers at the Fachhochschule Graub\u00fcnden in Switzerland have announced<\/a> 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.<\/p>\n

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

There is a long tradition of computing digits of $\\pi$.\u00a0 There is even an MSC2020<\/a> class for the family of such computations:\u00a0 11Y60<\/strong><\/a> Evaluation of number-theoretic constants<\/em>.\u00a0 Long ago, such computations were done by hand.\u00a0 Wikipedia has a nice page with the history of the computations,<\/a> and some related facts.\u00a0 Early mathematicians in Egypt, Babylon, and China had approximations for $\\pi$, usually as fractions.\u00a0 As a formalized system, continued fractions provide an accessible method for generating good rational approximations to irrational numbers, including $\\pi$.\u00a0 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<\/a> in the OEIS<\/a> is the continued fraction representation of $\\pi$, in the standard continued fraction shorthand.\u00a0 \u00a0Once we switched to using the decimal system, the digits became the target.\u00a0 \u00a0Various mathematicians, some unknown, some known, some famous, worked on computations of the digits of $\\pi$.\u00a0 Now, of course, we rely on computers, but we still need good algorithms.<\/p>\n

As a non-expert in this area, one result that I find particularly fascinating is<\/p>\n

MR1415794<\/a>
\nBailey, David<\/a> (1-NASA9); Borwein, Peter<\/a> (3-SFR); Plouffe, Simon<\/a> (3-SFR)
\nOn the rapid computation of various polylogarithmic constants. (English summary)
\nMath. Comp. 66 (1997), no. 218, 903\u2013913.
\n11Y60<\/a><\/p>\n

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

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

MR0877728<\/a>
\nBorwein, Jonathan M.<\/a> (3-DLHS); Borwein, Peter B.<\/a> (3-DLHS)
\nPi and the AGM.
\nA 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
\n11Y60<\/a> (68Q30<\/a>)<\/p>\n

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

Some reviews from MathSciNet<\/h2>\n
\n

MR1415794<\/a>
\nBailey, David<\/a> (1-NASA9); Borwein, Peter<\/a> (3-SFR); Plouffe, Simon<\/a> (3-SFR)
\nOn the rapid computation of various polylogarithmic constants. (English summary)
\nMath. Comp. 66 (1997), no. 218, 903\u2013913.
\n11Y60<\/a><\/p>\n

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.<\/p>\n

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,
\n$$
\nb^nC\\bmod1=\\sum_{k=0}^\\infty\\frac{b^{n-ck}}{q(k)}\\bmod1= \
\n\\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.
\n$$
\nIn 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.<\/p>\n

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)$.<\/p>\n

Reviewed by Andreas Guthmann<\/a><\/p>\n

\n

MR0877728<\/strong><\/a>
\nBorwein, Jonathan M.<\/a>\u00a0(3-DLHS)<\/a><\/span>;\u00a0Borwein, Peter B.<\/a>\u00a0(3-DLHS)<\/a><\/span>
\nPi and the AGM.<\/span>
\nA study in analytic number theory and computational complexity.\u00a0Canadian Mathematical Society Series of Monographs and Advanced Texts.<\/a>\u00a0A Wiley-Interscience Publication.\u00a0John Wiley & Sons, Inc., New York,<\/em>\u00a01987.\u00a0xvi<\/span>+414 pp. ISBN: 0-471-83138-7
\n11Y60 (68Q30)<\/a><\/p>\n

This book reveals the close relationship between the algebraic-geometric mean iteration and the calculation of\u00a0$\\pi$<\/span>.<\/p>\n

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$<\/span>\u00a0leads into the area of calculating algebraic functions, elementary functions and constants plus the transcendence of\u00a0$\\pi$<\/span>\u00a0and\u00a0$e$<\/span>. The calculation of\u00a0$\\pi$<\/span>\u00a0advanced with a frenzy with the advent of modern computers. Briefly, in 1706 the first 100 digits of\u00a0$\\pi$<\/span>\u00a0were calculated. By 1844 the first 205 digits were known. In 1947 the first 808 digits of\u00a0$\\pi$<\/span> were computed using a desk calculator.<\/p>\n

Then the modern computer came on the scene. Now the known first digits changed rapidly, which Table A partially illustrates:<\/p>\n\n\n\n\n\n\n\n\n\n
Table A:<\/th>\nYear<\/th>\nNumber of known
\nfirst digits of $\\pi$<\/th>\n		Required Time
\nto Calculate<\/th>\n<\/tr>\n
<\/td>\n1949<\/td>\n2\u00a0037<\/td>\n70 hours<\/td>\n<\/tr>\n
<\/td>\n1961<\/td>\n100\u00a0000<\/td>\n9 hours<\/td>\n<\/tr>\n
<\/td>\n1973<\/td>\n1\u00a0000\u00a0000<\/td>\n24 hours<\/td>\n<\/tr>\n
<\/td>\n1983<\/td>\n16\u00a0000\u00a0000<\/td>\n30 hours<\/td>\n<\/tr>\n
<\/td>\n1986<\/td>\n29\u00a0360\u00a0000<\/td>\n28 hours<\/td>\n<\/tr>\n
<\/td>\n1986<\/td>\n$2^{25}$=33\u00a0554\u00a0432<\/td>\n96 minutes<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n

These figures reveal, and Table B shows, how much the speed of computing has increased in a very short time.<\/p>\n\n\n\n\n\n\n\n\n\n
Table B:<\/th>\nYear<\/th>\nApproximate
\nDigits\/Hour<\/th>\n<\/tr>\n
<\/td>\n1949<\/td>\n29.1<\/td>\n<\/tr>\n
<\/td>\n1961<\/td>\n11\u00a0111.1<\/td>\n<\/tr>\n
<\/td>\n1973<\/td>\n41\u00a0666.7<\/td>\n<\/tr>\n
<\/td>\n1983<\/td>\n533\u00a0333.3<\/td>\n<\/tr>\n
<\/td>\n1986<\/td>\n1\u00a0048\u00a0571.4<\/td>\n<\/tr>\n
<\/td>\n1986<\/td>\n20\u00a0971\u00a0520.0<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n

Reviewed by\u00a0H. London<\/a><\/p>\n

\n

MR1021452<\/strong><\/a>
\nChudnovsky, D. V.<\/a>\u00a0(1-CLMB)<\/a><\/span>;\u00a0Chudnovsky, G. V.<\/a>\u00a0(1-CLMB)<\/a><\/span>
\nThe computation of classical constants.<\/span>
\nProc. Nat. Acad. Sci. U.S.A.<\/em><\/a>\u00a086\u00a0<\/a>(1989),\u00a0<\/a>no. 21,<\/a>\u00a08178\u20138182.
\n11Y60 (11-04 11Y35 33A99)<\/a><\/p>\n

In this very interesting paper the authors make a large number of valuable comments on mathematics and algorithmics in connection with their computation of\u00a0$\\pi$<\/span>\u00a0up to one billion digits. They give a short history of the computation of\u00a0$\\pi$<\/span>\u00a0and 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\u00a0$\\pi$<\/span>. Finally, some remarks on computer implementations are made.<\/p>\n

Reviewed by\u00a0F. Beukers<\/a><\/span><\/p>\n

\n

MR1222488<\/strong><\/a>
\nBorwein, J. M.<\/a>\u00a0(3-WTRL-B)<\/a><\/span>;\u00a0Borwein, P. B.<\/a>\u00a0(3-DLHS)<\/a><\/span>
\nClass number three Ramanujan type series for\u00a0$1\/\\pi$<\/span>.<\/span>\u00a0(English summary)<\/span>
\nComputational complex analysis.
\nJ. Comput. Appl. Math.<\/em><\/a>\u00a046\u00a0<\/a>(1993),\u00a0<\/a>no. 1-2,<\/a>\u00a0281\u2013290.
\n11Y60 (11R11)<\/a><\/p>\n

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

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

{For the collection containing this paper see\u00a0MR1222468<\/a>.}<\/span><\/p>\n

Reviewed by\u00a0Andrew Granville<\/a><\/span><\/p>\n

<\/div>","protected":false},"excerpt":{"rendered":"

Researchers at the Fachhochschule Graub\u00fcnden 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.<\/p>\n

<\/div>\n","protected":false},"author":86,"featured_media":0,"comment_status":"open","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"jetpack_post_was_ever_published":false,"_jetpack_newsletter_access":"","_jetpack_dont_email_post_to_subs":false,"_jetpack_newsletter_tier_id":0,"_jetpack_memberships_contains_paywalled_content":false,"_jetpack_memberships_contains_paid_content":false,"footnotes":""},"categories":[35],"tags":[],"class_list":["post-3238","post","type-post","status-publish","format-standard","hentry","category-mathematics-in-the-news"],"jetpack_featured_media_url":"","jetpack_shortlink":"https:\/\/wp.me\/p6C2KK-Qe","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/blogs.ams.org\/beyondreviews\/wp-json\/wp\/v2\/posts\/3238","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/blogs.ams.org\/beyondreviews\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/blogs.ams.org\/beyondreviews\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/blogs.ams.org\/beyondreviews\/wp-json\/wp\/v2\/users\/86"}],"replies":[{"embeddable":true,"href":"https:\/\/blogs.ams.org\/beyondreviews\/wp-json\/wp\/v2\/comments?post=3238"}],"version-history":[{"count":42,"href":"https:\/\/blogs.ams.org\/beyondreviews\/wp-json\/wp\/v2\/posts\/3238\/revisions"}],"predecessor-version":[{"id":3282,"href":"https:\/\/blogs.ams.org\/beyondreviews\/wp-json\/wp\/v2\/posts\/3238\/revisions\/3282"}],"wp:attachment":[{"href":"https:\/\/blogs.ams.org\/beyondreviews\/wp-json\/wp\/v2\/media?parent=3238"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/blogs.ams.org\/beyondreviews\/wp-json\/wp\/v2\/categories?post=3238"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/blogs.ams.org\/beyondreviews\/wp-json\/wp\/v2\/tags?post=3238"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}