{"id":487,"date":"2019-06-29T22:00:18","date_gmt":"2019-06-29T22:00:18","guid":{"rendered":"http:\/\/funfacts.104.42.120.246.xip.io\/?page_id=487"},"modified":"2019-11-20T22:13:50","modified_gmt":"2019-11-20T22:13:50","slug":"finding-the-n-th-digit-of-pi","status":"publish","type":"page","link":"https:\/\/math.hmc.edu\/funfacts\/finding-the-n-th-digit-of-pi\/","title":{"rendered":"Finding the N-th digit of Pi"},"content":{"rendered":"\n

Here is a very interesting formula for pi, discovered by David Bailey, Peter Borwein, and Simon Plouffe in 1995:
Pi = SUMk=0 to infinity<\/sub> 16-k<\/sup> [ 4\/(8k+1) – 2\/(8k+4) – 1\/(8k+5) – 1\/(8k+6) ].
The reason this pi formula is so interesting is because it can be used to calculate the N-th digit of Pi (in base 16) without having to calculate all of the previous digits<\/em>!<\/p>\n\n\n\n

Moreover, one can even do the calculation in a time that is essentially linear in N, with memory requirements only logarithmic in N. This is far better than previous algorithms for finding the N-th digit of Pi, which required keeping track of all the previous digits!<\/p>\n\n\n\n

Presentation\u00a0Suggestions:<\/strong>
You might start off by asking students how they might calculate the 100-th digit of pi using one of the other\u00a0pi formulas they have learned. Then show them this one…<\/p>\n\n\n\n

The Math Behind the Fact:<\/strong>
Here’s a sketch of how the BBP formula can be used to find the N-th hexadecimal digit of Pi. For simplicity, consider just the first of the sums in the expression, and multiply this by 16N<\/sup>. We are interested in the fractional part of this expression. The numerator of a given term in this sum is 16N-k<\/sup>, and it can be evaluated very easily mod (8k+1) using a binary algorithm for exponentiation. Division by (8k+1) is straightforward via floating point arithmetic. Not many more than N terms of this sum need be evaluated, since the numerator decreases very quickly as k gets large so that terms become negligible. The other sums in the BBP formula are handled similarly. This yields the hexadecimal expansion of Pi starting at the (N+1)-th digit. More details can be found in the Bailey-Borwein-Plouffe reference.<\/p>\n\n\n\n

The BBP formula was discovered using the PSLQ Integer Relation Algorithm. However, the Adamchik-Wagon reference shows how similar relations can be discovered in a way that the proof accompanies the discovery, and gives a 3-term formula for a base 4 analogue of the BBP result.<\/p>\n\n\n\n

How to Cite this Page:<\/strong> 
Su, Francis E., et al. “Finding the N-th digit of Pi.” Math Fun Facts<\/em>. <http:\/\/www.math.hmc.edu\/funfacts>.<\/p>\n\n\n\n

References:<\/strong>
David Bailey, Peter Borwein, and Simon Plouffe. “On the rapid computation of various polylogarithmic constants”, Math. Comp. 66<\/em>(1997), 903-913.

Victor Adamchik and Stan Wagon, “A simple formula for pi”, Amer. Math. Monthly 104<\/em>(1997), 852-855.<\/p>\n\n\n\n

Fun Fact suggested by: <\/strong>
Arthur Benjamin <\/p>\n","protected":false},"excerpt":{"rendered":"

Here is a very interesting formula for pi, discovered by David Bailey, Peter Borwein, and Simon Plouffe in 1995:Pi =...<\/p>\n","protected":false},"author":7,"featured_media":0,"parent":0,"menu_order":0,"comment_status":"closed","ping_status":"closed","template":"","meta":{"footnotes":""},"tags":[31,4,10,12,29,30],"class_list":["post-487","page","type-page","status-publish","hentry","tag-computational-mathematics","tag-medium","tag-numtheory","tag-other","tag-pi","tag-pi-formula"],"jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/math.hmc.edu\/funfacts\/wp-json\/wp\/v2\/pages\/487","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/math.hmc.edu\/funfacts\/wp-json\/wp\/v2\/pages"}],"about":[{"href":"https:\/\/math.hmc.edu\/funfacts\/wp-json\/wp\/v2\/types\/page"}],"author":[{"embeddable":true,"href":"https:\/\/math.hmc.edu\/funfacts\/wp-json\/wp\/v2\/users\/7"}],"replies":[{"embeddable":true,"href":"https:\/\/math.hmc.edu\/funfacts\/wp-json\/wp\/v2\/comments?post=487"}],"version-history":[{"count":4,"href":"https:\/\/math.hmc.edu\/funfacts\/wp-json\/wp\/v2\/pages\/487\/revisions"}],"predecessor-version":[{"id":1439,"href":"https:\/\/math.hmc.edu\/funfacts\/wp-json\/wp\/v2\/pages\/487\/revisions\/1439"}],"wp:attachment":[{"href":"https:\/\/math.hmc.edu\/funfacts\/wp-json\/wp\/v2\/media?parent=487"}],"wp:term":[{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/math.hmc.edu\/funfacts\/wp-json\/wp\/v2\/tags?post=487"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}