7

I am looking for a formula/algorithm to calculate PI~3.14 in a given precision.

The formula/algorithm must have only very basic arithmetic as

  • +: Addition
  • -: Subtraction
  • *: Multiplication
  • /: Divison

because I want to implement these operations in C++ and want to keep the implementation as simple as possible (no bignum library is allowed).

I have found that this formula for calculating Pi is pretty simple:

Pi/4 = 1 - 1/3 + 1/5 - 1/7 + ...  = sum( (-1)^(k+1)/(2*k-1) , k=1..inf )

(note that (-1)^(k+1) can be implemented easily by above operators).

But the problem about this formula is the inability to specify the number of digits to calculate. In other words, there is no direct way to determine when to stop the calculation.

Maybe a workaround to this problem is calculating the difference between n-1th and nth calculated term and considering it as the current error.

Anyway, I am looking for a formula/algorithm that have these properties and also converges faster to Pi

Isaac
  • 2,332
  • 6
  • 33
  • 59
  • 1
    there are dozens of formulas which you can try here, and most of them converge pretty fast http://en.wikipedia.org/wiki/Pi – Gabi Purcaru Dec 19 '10 at 18:43
  • @Gabi: but most of them contain non-basic operations like `square root`. i am looking for a formula based on the `+`,`-`,`*`, and `/`. Please, please read all of the question. – Isaac Dec 19 '10 at 18:45
  • Here's another wikipedia source that should help: http://en.wikipedia.org/wiki/Numerical_approximations_of_%CF%80. (And many are sum formulas using basic operators) – Seth Dec 19 '10 at 18:48
  • possible duplicate of [Fastest way to get value of pi](http://stackoverflow.com/questions/19/fastest-way-to-get-value-of-pi) – Jason S Dec 19 '10 at 22:05
  • I don't see the connection between wanting only 'simple' arithmetic ops and avoiding a bignum library: the standard C library contains a lot more than those operations, and you're going to have trouble calculating arbitrary digits without a bignum library regardless of what you use. – Nick Johnson Dec 19 '10 at 22:45
  • @Nick: There is really a connection: I have to implement all of it by myself, so i prefer a formula with fewer type of operations because I needs less programming effort. – Isaac Dec 20 '10 at 09:50
  • @Jason: it's not duplicate. i am seeking for a algorithm with simple arithmetics to calculate Pi (with any arbitrary precision). – Isaac Dec 20 '10 at 10:01
  • OK, perhaps not a duplicate of that particular question, but there have been several questions on stackoverflow for how to calculate pi. – Jason S Dec 20 '10 at 14:40
  • @Isaac More basic ops doesn't mean less programming effort. Which is simpler: n additions, or one multiplication? – Nick Johnson Dec 20 '10 at 20:23
  • @Nick: The numbers must be stored in the strings (standard variable types in C++ only support a limited precision), Then I have to implement any used operator by myself. Therefore, I prefer to have less operators (that means less implementation). Note that the variables are decimal, so I cannot use `Addition` for multiplication. – Isaac Dec 21 '10 at 21:40
  • @Isaac Why not just ask how to generate digits of pi to arbitrary precision, then? You're assuming the answer will involve math on strings, when there are undoubtedly much better methods. – Nick Johnson Dec 22 '10 at 03:43

3 Answers3

6

Codepad link:

#include <iostream>
#include <cmath>
int main()
{
    double p16 = 1, pi = 0, precision = 10;

    for(int k=0; k<=precision; k++)
    {
        pi += 1.0/p16 * (4.0/(8*k + 1) - 2.0/(8*k + 4) - 1.0/(8*k + 5) - 1.0/(8*k+6));
        p16 *= 16;
    }
    std::cout<<std::setprecision(80)<<pi<<'\n'<<M_PI;
}

Output:

3.141592653589793115997963468544185161590576171875
3.141592653589793115997963468544185161590576171875

This is actually the Bailey-Borwein-Plouffe formula, also taken from the link from wikipedia.

Gabi Purcaru
  • 30,940
  • 9
  • 79
  • 95
  • This formula is well-known as one of the formulas that gives `n`th digit of Pi, without the need of calculating `n-1` digits before it. Then, is this formula relatively efficient (in respect to the other formulas) to calculate all n digits? – Isaac Dec 19 '10 at 19:06
  • @Isaac I didn't test all of them, but if after 11 steps it finds the first 15 digits, do you still need better performance? (_all the 15 digits are correct_) – Gabi Purcaru Dec 19 '10 at 19:12
  • 11 step for 15 digits seems really, really good! compared to the given summation in the question which needs 300 terms to calculate 2 decimal points! Anyway, I wonder the ability of `BBP` formula to immediately calculate `n`th digit of `Pi` may have impact on the performance of calculating all digits of `Pi` to `n`. – Isaac Dec 19 '10 at 19:33
  • @Isaac I'm not the man to say whether or not it could have an impact, but it seems it works very well, so IMO it's ok. Also, I updated the answer with C code and comparison with `M_PI` – Gabi Purcaru Dec 19 '10 at 19:43
  • nice answer by the way. (although it cannot calculate Pi for big `n` s). – Isaac Dec 19 '10 at 20:33
3

In your original (slowly converging) example, the error term can be computed because this is an alternating series; see http://en.wikipedia.org/wiki/Alternating_series#Approximating_Sums

Essentially, the next uncomputed term is a bound on the error.

Keith
  • 6,756
  • 19
  • 23
-2

You can just do the Taylor envelope of the arctan(1) and then you will get pi/4 just summing all the rest part. The taylor envelope of arctan(1)

http://en.wikipedia.org/wiki/Taylor_series

also you can use the euler formula with z=1 and then multiply the result by 4.

http://upload.wikimedia.org/math/2/7/9/279bed5a2ea3b80a71f5b22078090168.png

user2402192
  • 1
  • The arctan formula is just the equation OP started with (which converges extremely slowly, btw). – Teepeemm Oct 08 '14 at 02:40
  • Not if you sum the remains. Summing all remains will give a complete value too, until you start with the #0 – user2402192 Jan 22 '15 at 23:22
  • "remains" aren't a real thing. Are you talking about the remainder term of the Taylor series? I don't know what you mean by summing that. – Teepeemm Sep 02 '15 at 21:38