使用倒数平方和计算圆周率

Question

我需要使用以下公式预定义精度来计算PI： 于是我得出了这个解决方案。

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;
}

这个公式是正确的，但它的效率存在问题。当精度值为8或更高时，速度非常慢。

有没有更好（且更快！）的方法来使用该公式计算PI值？

- Pavlo Zin

---

只执行一次的话，它真的会慢到成为问题吗？ - Scott Hunter

尝试在 for 循环语句中使用 int。我怀疑在那里使用双精度会使你的速度明显变慢。 - Sopuli

@ScottHunter 是的，它很慢。看看numberOfSumElements变量以及它如何依赖于精度。 - Pavlo Zin

只要precision不超过8（否则Pow(10, presicion + 2)会溢出int），@Sopuli建议使用int循环变量是好的。您还需要更改sum + =行上的1为1.0以获得正确的结果，并将numberOfSumElements更改为int（在赋值时进行适当的类型转换）以获得最大的受益。 - Joe White

请大家阅读公式和代码。当精度>=8时，OP抱怨循环速度慢，而该循环被运行了10^10次！这是一百亿次迭代。当然会运行缓慢。 - Pieter Geerkens

Answer 1

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

我将严格按照实际软件工程术语来讲解，避免陷入形式化数学中。这些都是任何软件工程师都应该知道的实用技巧。

首先观察您的代码的复杂性。执行所需的时间严格由此表达式确定。您编写了一种指数算法，您计算的值随着精度的提高而迅速上升。您引用了一个令人不安的数字，8会产生10^10或进行十亿次计算的循环。是的，您注意到了这一点，这时计算机开始花费几秒钟的时间来产生结果，无论它们有多快。

指数算法非常糟糕，它们的性能非常差。如果使用阶乘复杂度O(n!)更糟糕，那么您只能做得更糟。否则就是许多现实世界问题的复杂性。

现在，这个表达式是否准确？您可以通过使用一个实用的手算例子来进行“肘部测试”。让我们选择5位数的精度作为目标并写出它：

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

你可以看出这些加数迅速变小，它会快速收敛。你可以推断出，一旦你要添加的下一个数字足够小，那么它对于使结果更准确的作用就非常小了。假设当下一个数字小于0.00001时，就是停止尝试改进结果的时候了。

因此，你将在 1 / (n * n) = 0.00001 => n * n = 100000 => n = sqrt(100000) => n ~= 316 处停止。

你的表达式说要在10^(5+2) = 10,000,000处停止。

你可以看出你完全错了，循环次数过多，而且最后999万次迭代没有提高结果的准确性。

---

是时候谈谈真正的问题了，可惜你没有解释如何得出如此严重错误的算法。但是肯定在测试代码时发现它并不擅长计算更精确的π值。所以你认为通过更频繁地迭代，可以获得更好的结果。

请注意，在这个弯曲测试中，能够用足够的精度计算加法也非常重要。我故意四舍五入数字，仿佛是在一台能够执行5位数字精度的机器上计算的。无论你做什么，结果都不能比5位数更精确。

你的代码中使用了“double”类型。由处理器直接支持，它没有无限的精度。你需要记住的唯一规则是，“double”计算永远不会比15位数更精确。同时也需要记忆“float”的规则，它永远不会比7位数更精确。

无论您为 presicion 传递什么值，结果都不能比 15 位更精确。这完全没有用，您已经准确地知道了圆周率的价值，它是 Math.Pi。

要解决这个问题，您需要使用比 double 更精确的类型。实际上，它需要是一种具有任意精度的类型，至少与您传递的 presicion 值一样准确。在 .NET 框架中不存在这样的类型。在 SO 上找到一个可以提供此类类型的库是一个常见问题。

- Hans Passant