Estimating pi using while loop for specific tolerence.

So my task is to calculate an estimate of pi within a specific tolerence using a while loop. For a tolerence up to 10^-5, my code runs fine however anything above that and the number of iterations it takes to be within tolerence is far too high.

The 'A' matrix is used to store the Nth iteration and it's respective pi-estimate value to be used for another part of the assignment. I've attached images of my code and the summation formula I am supposed to use. I'm hoping someone can provide a tip and show me where I'm going wrong here & how to bring the number of iterations down. Thanks for your help.

[KSSV]

I don't think there is any issue. It is obvious that the more tolerance, the more closer the value and the more it needs N and the more iterations it takes.

[Jose Escobar]

Yes, however the higher tolerances require massive amounts of time to compute an answer (>1hr) for the massive number of iterations needed for an acceptable pi-value. As I need to compute a value for tolerences of 10^-4,10^-5..up to 10^-12 this code would take hours. At first I figured I'd just let it run overnight, however I asked a classmate and he said he was having the same issue until a TA wrote a different code for him which brought the # of iterations down. For example for a tolerence of 10^-4 my code requires 9549 iterations whereas his was around 90. So I was hoping to find a different way of approaching this problem.

Answer 1

[James Tursa]

For starters, if you are taking the tolerance out to 12 digits and beyond, you need to use a more accurate value of pi for your comparison. You are using:

3.141592653590 <-- a close approximation of pi only accurate to 12 digits, not full double precision accuracy

You should be using as many significant digits as possible for this if you are going to take the process out to nearly the limits of double precision. So use pi, or maybe a literal 3.1415926535897932

Also, if you are looking for speed, DON'T display anything inside the loop! Of course, you could get rid of the loop entirely and vectorize things to gain more speed. E.g.

N = 10000000;
v = 1:N;
q = 1./(v.^2);
Pisum = sqrt(6*cumsum(q));

[Jose Escobar]

Thank you! This was very helpful. Thanks to everyone else that replied as well, you are all awesome. :)

Answer 2

[Roger Stafford]

The difference between the finite sum 1+1/4+1/9+...+1/N^2 and the infinite sum is proportional to 1/N. Therefore each time you divide the tolerance by ten you multiply the required number of terms in the finite sum by ten. Thus, if you are required to use this approximation, you are stuck with this kind of increase in the needed iteration count.

However you can reduce the time required by not dividing by 6 and taking the square root at each step, but only when you want to to check the answer. That is, you could take a thousand steps, for example, and only then divide by 6, take the square root, and check the answer. That would save a lot of useless repetitive computation.

Answer 3

[Guillaume]

Please don't post picture of your code, we can't copy/paste it. There's a {} Code button to format pasted text as code.

Roger has already explained why there's not much you can do about the runtime of your code, it's tied to the algorithm you use. I'm just going to point out that you have one obvious slow down in your code:

for ii = 1:N  %gaah! can't copy paste!
  A(N, 1) = N;
  A(N, 2) = PiSum;
end

This just copy N times the same two values in the same two elements of A. The only effect of this loop is to make each iteration slower than the previous one.