Math Fun Facts!
hosted by the Harvey Mudd College Math Department created, authored and ©1999-2010 by Francis Su
Subscribe to our RSS feed   or follow us on Twitter.
Get a random Fun Fact!
or
No subject limitations
Search only in selected subjects
    Algebra
    Calculus or Analysis
    Combinatorics
    Geometry
    Number Theory
    Probability
    Topology
    Other subjects
  Select Difficulty  
Enter keywords 

  The Math Fun Facts App!
 
  List All : List Recent : List Popular
  About Math Fun Facts / How to Use
  Contributors / Fun Facts Home
© 1999-2010 by Francis Edward Su
All rights reserved.

From the Fun Fact files, here is a Fun Fact at the Medium level:

Finding the N-th digit of Pi

Here is a very interesting formula for pi, discovered by David Bailey, Peter Borwein, and Simon Plouffe in 1995:


Pi = SUMk=0 to infinity 16-k [ 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!

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!

Presentation Suggestions:
You might start off by asking students how they might calculate the 100-th digit of pi using one of the other pi formulas they have learned. Then show them this one...

The Math Behind the Fact:
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. We are interested in the fractional part of this expression. The numerator of a given term in this sum is 16N-k, 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.

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.

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

Share

References:
    David Bailey, Peter Borwein, and Simon Plouffe. "On the rapid computation of various polylogarithmic constants", Math. Comp. 66(1997), 903-913.

    Victor Adamchik and Stan Wagon, "A simple formula for pi", Amer. Math. Monthly 104(1997), 852-855.


Keywords:    number theory, computational mathematics
Subjects:    number theory
Level:    Medium
Fun Fact suggested by:   Francis Su
Suggestions? Use this form.
4.24
 
current
rating 		Click to rate this Fun Fact...
    *   Awesome! I totally dig it!
    *   Fun enough to tell a friend!
    *   Mildly interesting
    *   Not really noteworthy
and see the most popular Facts!
Get the Math Fun Facts
iPhone App!

Want another Math Fun Fact?

For more fun, tour the Mathematics Department at Harvey Mudd College!