Sum of sequence precision

Question

I came up with this answer in stackoverflow. It states a question:

Given that Pi can be estimated using the function 4 * (1 - 1/3 + 1/5 - 1/7 + ...) 
with more terms giving greater accuracy, write a function that calculates Pi to 
an accuracy of 5 decimal places.

I once knew how to do things like that but now it is all white space in my brains. Moreover, I cannot figure out what to google for so I get the needed algorithm. This link, however, tells it is using a graph calculator, which isn't helpful at all.

Answer 1

First of all, this is a terrible way to compute $\pi$. That said, you have a series satisfying the hypotheses of the alternating series test. In particular this means that

$$ \left| \pi - 4\sum_{k=0}^n \frac{(-1)^k}{2k+1} \right| < \frac{4}{2n+3}, $$ i.e. the error in the approximation is less than the first omitted term. (This is not true for general series!)

If you want five correct decimal places, you need to guarantee that the error is less than $5\times 10^{-6}$, so you want to choose $n$ such that

$$ \frac{4}{2n+3} < 5\times 10^{-6} \quad\Rightarrow\quad n > 399,999. $$

I'll leave the actual implementation as a suitable loop up to you. If you don't want to do the computatation of $n$ beforehand, just loop until the next term is small enough. Again, this approach relies on the alternating series test.

Answer 2

You can brute force sum the series using about 200000 terms (for accuracy reason best summed backwards), or you can look at the Example 6 of your PDF. If you want better methods, some keywords for your search are series acceleration (see e.g. http://en.wikipedia.org/wiki/Series_acceleration as a starting point) or sequence transformation.

Answer 3

I think this small problem is misleading.

A couple of observations:

• About the phrase "an accuracy of $x$ decimal places": it's not enough to have computed $\pi$ with great accuracy to ensure that you have $x$ accurate decimal digits. For instance, $0.499999$ is very close to $0.5$, but not even the first decimal digit is correct.
• The information that "more terms give greater accuracy" is not sufficient.

The first point is not really a big deal, it can be worked around. In any case it's preferable to talk of a "max error" (rather than accurate decimal places). Requiring that the error is no greater than $5\times 10^{-6}$ does ensures that the difference between your approximation and $\pi$ rounded off to 5 decimal places is zero, though.

The second point is more problematic. Knowing that more terms give greater accuracy is not good enough (to know when you can stop computing) (*), you need to know something about the speed of convergence. In this particular case, we can estimate the error (knowing some mathematics) because the series is alternating, as mrf pointed out. It turns out that the following algorithm works for alternating series:

res = 0;
nextTerm = // first term, here: 4;
i = 1;
while (abs(nextTerm) > error)
    res = res + nextTerm;
    nextTerm = // some expression, here: 4*(-1)^i / (2*i + 1);
    i = i + 1;
end while
return res;

Out of interest, I should also point out like mrf that this algorithm to compute $\pi$ is very slow in practice, there are far more efficient algorithms, thankfully.

(*) that is, unless you know $\pi$ somehow. For instance, I suppose the following small problem would be acceptable: your program has a constant Pi (for instance M_PI in C/C++) that you are not allowed to display, so you don't know its decimal digits. Write a function which approximates Pi with an error no bigger than error (given explicitely, e.g. 0.00001).