Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

In this message at point 18 I saw following programming question:

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

So I know how to implement the given function and how to choose how "far" I should calculate, but how can I tell when I've reached the "accuracy of 5 decimal places" ?

share|improve this question
1  
That converges quite slowly, I believe; Wikipedia states it'll take 500,000 iterations to get to 5 places. You'd have to read the linked paper to find out how they determined that though. :-P –  Martijn Pieters Aug 30 '12 at 9:07
1  
This is a math question –  Simon Aug 30 '12 at 14:06
    
Just use a constant. The value of PI to 5 decimal places is known. In many cases its already a math constant. The programming question seems to ignore this fact. –  Ramhound Aug 30 '12 at 14:35
    
@Ramhound - That's because the programming question is a sample interview question. Of course in your daily work you'd use a built-in or define your own. That wasn't the point; any idiot can hard-code the desired result of a single trial into a method. The point was to determine if you can think your way through the desired algorithm. –  KeithS Aug 30 '12 at 15:44
    
What do you mean when you say "I know... how to choose how 'far' I should calculate"? Because that's precisely the question you are asking. –  Sridhar Ramesh Aug 30 '12 at 17:16
show 1 more comment

migrated from programmers.stackexchange.com Aug 30 '12 at 16:14

This question came from our site for professional programmers interested in conceptual questions about software development.

6 Answers

up vote 4 down vote accepted

The series you wrote is an Alternating series. The alternating series test says that for such a series, the error in the approximation is less than the absolute value of the first missing term.

In other words, if the last term you have is of the form $\pm \frac{1}{2n+1}$, then your approximation is good within $\frac{1}{2n+3}$. To be sure that this is accurate to the 5th digit, you need

$$\frac{1}{2n+3} \leq 0.00001$$

share|improve this answer
    
You are correct about the alternating series test and the error bound. One has to be careful by what is meant by accurate to 5 decimal places (which may be more an English problem than a math one). If $\pi$ were of the form $3.1416000000001233144\ldots$ you could have quite a small error change the fifth decimal point. Yes, you would have to be really unlucky. –  Ross Millikan Sep 4 '12 at 15:53
add comment

You alternate adding and subtracting decreasing values. So the next value is an upper bound of the difference between your current result and Pi.

share|improve this answer
    
Now it seems obvious, thanks... –  pgras Aug 30 '12 at 9:36
add comment

You can just keep going until the decimal places you are interested in don't change for two terms. Since we add and subtract alternately, and subsequent terms have less effect, you can be sure that the decimal places will never change if they don't for two turns.

Note that this series for pi is very slow!

share|improve this answer
add comment

4 * 1 / 400000 = 0.00001. Any term smaller than that will not contribute to the first 5 decimal places of the accumulated sum.

So in pseudo-code:

val = 0;
for d = 1; d <= 400000; d += 4
    val += 1 / d
    val -= 1 / (d+2)
return val*4 
share|improve this answer
4  
-1 Incomplete. You need to show that the terms smaller than 1E-5 don't sum to more than 1E-5. In fact, actually it's even more complicated than that, because the answer should be correctly rounded. You also potentially have loss of significance due to adding from the largest elements in the series rather than from the smallest. –  Peter Taylor Aug 30 '12 at 12:46
add comment

What you talk about is usually called Taylor series. Calculation is simple. Just add more terms until you reach the point, that terms don't add more accuracy for your desired precision.

share|improve this answer
add comment

The iteration should be simple; it's how you know when you're done, without knowing the answer, that's trickier. Basically, if you need to know the answer to 5 decimal places, then stop as soon as the 5th decimal place hasn't changed in some arbitrary number of trials.

A more elegant way (not requiring you to multiply by 4 after every step to ensure the precision of the final number is within the epsilon) is to quit as soon as you reach a value that does not change the least significant digit of the decimal value that would produce the correct value of Pi. Pi to 5 decimals is 3.14159. Divided by 4 (producing the necessary sum of the infinite series), that's .7853975. This is what you have to get to. Therefore, the largest fraction that can be summed to the series that will not affect the precision is 1E-8 (one hundred millionth).

So, the ending point is the iteration N at which $|\dfrac{-1}{2n-1} + \dfrac{1}{2n+1}| < .00000001$, so that at the end of the iteration (one iteration being a subtraction and an addition), the series sum has not changed by a greater degree than the epsilon. By inspection, we see that the sum of the two fractions will be negative, so:

$\dfrac{1}{2n+1} - \dfrac{1}{2n-1} = -0.00000001$

$\dfrac{2n-1}{(2n+1)(2n-1)} - \dfrac{2n+1}{(2n+1)(2n-1)} = -1*10^{-8}$

$\dfrac{(2n-1)-(2n+1)}{(2n+1)(2n-1)} = -1*10^{-8}$

$\dfrac{-2}{4n^2-1} = -1*10^{-8}$

$-2 = (-1*10^{-8})(4n^2-1)$

$\dfrac{-2}{-1*10^{-8}} = 4n^2-1$ <-- from here you can pretty much plug in any needed precision

$2*10^{8} = 4n^2-1$

$200000001/4 = n^2$

$50000000.25 = n^2$

$n > 7071$

Plugging this back in to check, we get $\dfrac{1}{2(7072)+1} - \dfrac{1}{2(7072)-1} = \dfrac{1}{14145} - \dfrac{1}{14143} = -0.9997*10^{-8}$ which is less significant than $-1*10^{-8}$.

So, it should take 7072 iterations, at least, of subtracting the inverse of an odd natural number, then adding the next smaller odd inverse, to arrive at a sum that will produce pi to the necessary precision. In fact, it may actually take many more to produce a value that rounds correctly to the necessary number of decimal places; if you simply truncate to the needed sig figs, this is the answer.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.