How is PI calculated?

Question

I want to make a function in C that can return PI to X places..

I'm just not sure how... Thanks

Edit: I don't care how slow it is I really just want an algorithm that will return PI at X decimal... Iv been looking at http://bellard.org/pi/ but I don't understand how to get the nth of Pi from this. Thanks

Answer 1

There are many algorithms for numeric approximation of π.

Answer 2

In calculus there is a thing called Taylor Series which provides an easy way to calculate many irrational values to arbitrary precision.

Pi/4 = 1 - 1/3 + 1/5 - 1/7 + ...
(from http://www.math.hmc.edu/funfacts/ffiles/30001.1-3.shtml )

Keep adding those terms until the number of digits of precision you want stabilize.

Taylor's theorem is a powerful tool, but the derivation of this series using the theorem is beyond the scope of the question. It's standard first-year university calculus and is easily googlable if you're interested in more detail.

Edit: I didn't mean to imply that this is the most practical method to calculate pi. That would depend on why you really need to do it. For practical purposes, you should just copy as many digits as you need from one of the many published versions. I was suggesting this as a simple introduction of how irrational values can be equated to infinite series.

Answer 3

You can tell the precision based on the last term you added (or subtracted). Since the amplitude of each term in Alan's sequence is always decreasing and each term alternates in sign, the sum won't change more than the last term.

Translating that babble: After adding 1/5, the sum won't change more than 1/5, so you are precise to within 1/5. Of course, you'll have to multiply this by 4, so you're really only precise to 4/5.

Unfortunately, math doesn't always translate easily into decimal digits.

Answer 4

Are you willing to look up values instead of computing them?

Since you didn't explicitly specify that your function has to calculate values, here's a possible solution if you are willing to have an upper limit on the number of digits it can "calculate":

// Initialize pis as far out as you want. 
// There are lots of places you can look up pi out to a specific # of digits.
double pis[] = {3.0, 3.1, 3.14, 3.141, 3.1416}; 

/* 
 * A function that returns pi out to a number of digits (up to a point)
 */
double CalcPi(int x)
{
    // NOTE: Should add range checking here. For now, do not access past end of pis[]
    return pis[x]; 
}

int main()
{
    // Loop through all the values of "pi at x digits" that we have.
    for (int ii=0; ii<(int)sizeof(pis)/sizeof(double); ii++)
    {
        double piAtXdigits = CalcPi(ii);
    }
}

Writing CalcPi() this way (if it meets your needs) has a side benefit of being equally screaming fast for any value of X within your upper limit.

Answer 5

Latest formula: http://en.wikipedia.org/wiki/Bellard%27s_formula

Answer 6

Try this algorithm. It's probably the fastest known algorithm that doesn't require arbitrary (read huge) precision floats, and can give you the result directly in base 10 (or any other).

Answer 7

As an alternative to JeffH's method of storing every variation, you can just store the maximum number of digits and cut off what you don't need:

#include <string>
#include <iostream>
using std::cout; using std::endl; using std::string;

// The first 99 decimal digits taken from:
// http://www.geom.uiuc.edu/~huberty/math5337/groupe/digits.html
// Add more as needed.
const string pi =
  "1415926535"
  "8979323846"
  "2643383279"
  "5028841971"
  "6939937510"
  "5820974944"
  "5923078164"
  "0628620899"
  "8628034825"
  "342117067";

// A function in C++ that returns pi to X places
string CalcPi(const size_t decimalDigitsCount) 
{
  string returnValue = "3";
  if (decimalDigitsCount > 0)
  {
    returnValue += "." + pi.substr(0, decimalDigitsCount);
  }
  return returnValue;
} 

int main()
{
  // Loop through all the values of "pi at x digits" that we have. 
  for (size_t i = 0; i <= pi.size(); ++i) 
  {
    cout << "pi(" << i << "): " << CalcPi(i) << endl;
  } 
}

http://codepad.org/6mqDa1zj

Answer 8

PI

                                    char
                                _3141592654[3141
      ],__3141[3141];_314159[31415],_3141[31415];main(){register char*
      _3_141,*_3_1415, *_3__1415; register int _314,_31415,__31415,*_31,
    _3_14159,__3_1415;*_3141592654=__31415=2,_3141592654[0][_3141592654
   -1]=1[__3141]=5;__3_1415=1;do{_3_14159=_314=0,__31415++;for( _31415
  =0;_31415<(3,14-4)*__31415;_31415++)_31415[_3141]=_314159[_31415]= -
1;_3141[*_314159=_3_14159]=_314;_3_141=_3141592654+__3_1415;_3_1415=
__3_1415    +__3141;for         (_31415 = 3141-
       __3_1415  ;          _31415;_31415--
       ,_3_141 ++,          _3_1415++){_314
       +=_314<<2 ;          _314<<=1;_314+=
      *_3_1415;_31           =_314159+_314;
      if(!(*_31+1)           )* _31 =_314 /
      __31415,_314           [_3141]=_314 %
      __31415 ;* (           _3__1415=_3_141
     )+= *_3_1415             = *_31;while(*
     _3__1415 >=              31415/3141 ) *
     _3__1415+= -             10,(*--_3__1415
    )++;_314=_314             [_3141]; if ( !
    _3_14159 && *             _3_1415)_3_14159
    =1,__3_1415 =             3141-_31415;}if(
    _314+(__31415              >>1)>=__31415 )
    while ( ++ *               _3_141==3141/314
       )*_3_141--=0            ;}while(_3_14159
       ) ; { char *            __3_14= "3.1415";
       write((3,1),            (--*__3_14,__3_14
       ),(_3_14159              ++,++_3_14159))+
      3.1415926; }              for ( _31415 = 1;
     _31415<3141-               1;_31415++)write(
    31415% 314-(                3,14),_3141592654[
  _31415    ] +                "0123456789","314"
  [ 3]+1)-_314;                puts((*_3141592654=0
,_3141592654))                  ;_314= *"3.141592";}

(copied from: here)

Answer 9

Here's a paper (PDF) which explores the curious relationship between a sequence of points on the complex plane and how computing their "Mandelbrot number" (for lack a better term ... the number of iterations required to determine that the points in the sequence are not members of the Mandelbrot set) relates to PI.

Practical? Probably not.

Unexpected and interesting? I think so.

Answer 10

I believe the algorithm you're looking for is what's known as a "Spigot Algorithm." One particular kind is the BBP (Bailey-Borwein-Plouffe) formula.

I believe that's what you're looking for.