Calculate PI using the sum of inverse squares

Question

I need to calculate PI with predetermined precision using this formula:

So, I am done with this solution.

private static double CalculatePIWithPrecision(int presicion) { if (presicion == 0) { return PI_ZERO_PRECISION; } double sum = 0; double numberOfSumElements = Math.Pow(10, presicion + 2); for (double i = 1; i < numberOfSumElements; i++) { sum += 1 / (i * i); } double pi = Math.Sqrt(sum * 6); return pi; } 

So this works correctly, but I ran into a performance issue. It is very slow with an accuracy of 8 and higher.

Is there a better (and faster!) Way to calculate PI using this formula?

Answer 1

  double numberOfSumElements = Math.Pow(10, presicion + 2); 

I am going to talk about this strictly in the practical conditions of software development, avoiding the loss in formal mathematics. Just practical tips that any software engineer should know.

First check the complexity of the code. The duration of this execution is strictly determined by this expression. You wrote an exponential algorithm, the value that you calculate very quickly increases as the number of candidates increases. You quote an inconvenient number, 8 produces 10 ^ 10 or a cycle that is ten billion calculations. Yes, you notice that when computers start taking seconds to get results, no matter how fast they are.

Exponential algorithms are bad; they work very poorly. You can only do worse with factor complexity, O (n!), Which is growing even faster. Otherwise, the complexity of many real problems.

Now, is this an expression? You can do this with the “elbow test” using a practical feedback example. Let me select 5-digit accuracy as the target and write it down:

  1.0000 + 0.2500 + 0.1111 + 0.0625 + 0.0400 + 0.0278 + ... = 1.6433 

You can say that additions are rapidly decreasing, it is converging quickly. You can understand that as soon as the next number you add becomes small enough, it does very little to make the result more accurate. Let's say that when the next number is less than 0.00001, then it's time to stop trying to improve the result.

So, you will stop at 1 / (n * n) = 0.00001 => n * n = 100000 => n = sqrt (100000) => n ~ = 316

Your expression says to stop at 10 ^ (5 + 2) = 10,000,000

You can say that you are gone, loops too often and do not improve the accuracy of the result with the last 9.999 million iterations.

---

Time to talk about a real problem is too bad that you did not explain how you got into such a radically incorrect algorithm. But, of course, you found that when testing your code, it is just not very good at calculating a more accurate value for pi. Therefore, you decided that by repeating more often, you will get the best result.

Note that in this elbow test it is very important that you can calculate the additions with sufficient accuracy. I deliberately rounded the numbers, as if it were calculated on a machine capable of completing additions with an accuracy of 5 digits. Whatever you do, the result can never be more accurate than 5 digits.

The code uses a double type. Directly supported by the processor, it does not have infinite accuracy. The only rule you need to keep in mind is that double calculations are never more accurate than 15 digits. Also remember the rule for float, it is no more accurate than 7 digits.

So, no matter what value you pass to the destination, the result can never be more accurate than 15 digits. This is not useful at all, you already have a pi value accurate to 15 digits. This is Math.Pi

The only thing you need to do to fix this is to use the type with higher precision than double. In fact, it should be a type that has arbitrary precision, it should be at least accurate, like the value you passed. This type does not exist in the .NET framework. Finding a library that can provide you with one is a common question in SO.