Calculate PI using sum of inverse squares

Question

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

So I ended up 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 correct, but I faced the problem with efficiency. It's very slow with precision values 8 and higher.

Is there a better (and faster!) way to calculate PI using that formula?

Answer 1

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

I'm going to talk about this strictly in practical software engineering terms, avoiding getting lost in the formal math. Just practical tips that any software engineer should know.

First observe the complexity of your code. How long it takes to execute is strictly determined by this expression. You've written an exponential algorithm, the value you calculate very rapidly goes up as presicion increases. You quote the uncomfortable number, 8 produces 10^10 or a loop that makes ten billion calculations. Yes, you notice this, that's when computers starts to take seconds to produce a result, no matter how fast they are.

Exponential algorithms are bad, they perform very poorly. You can only do worse with one that has factorial complexity, O(n!), that goes up even faster. Otherwise the complexity of many real-world problems.

Now, is that expression actually accurate? You can do this with an "elbow test", using a practical back-of-the-envelope example. Let's pick a precision of 5 digits as a target and write it out:

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

You can tell that the additions rapidly get smaller, it converges quickly. You can reason out that, once the next number you add gets small enough then 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'll 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 tell that you are way off, looping entirely too often and not improving the accuracy of the result with the last 9.999 million iterations.

---

Time to talk about the real problem, too bad that you didn't explain how you got to such a drastically wrong algorithm. But surely you discovered when testing your code that it just was not very good at calculating a more precise value for pi. So you figured that by iterating more often, you'd get a better result.

Do note that in this elbow-test, it is also very important that you are able to calculate the additions with sufficient precision. I intentionally rounded the numbers, as though it was calculated on a machine capable of performing additions with 5 digits of precision. Whatever you do, the result can never be more precise than 5 digits.

You are using the double type in your code. Directly supported by the processor, it does not have infinite precision. The one and only rule you ever need to keep in mind is that calculations with double are never more precise than 15 digits. Also memorize the rule for float, it is never more precise than 7 digits.

So no matter what value you pass for presicion, the result can never be more precise than 15 digits. That is not useful at all, you already have the value of pi accurate to 15 digits. It is Math.Pi

The one thing you need to do to fix this is using a type that has more precision than double. In fact, it needs to be a type that has arbitrary precision, it needs to be at least as accurate as the presicion value you pass. Such a type does not exist in the .NET framework. Finding a library that can provide you with one is a common question at SO.