c# - 使用平方反比和计算 PI

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？

Answer 1

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

我将严格以实用的软件工程术语来讨论这个问题，避免迷失在正式的数学中。只是任何软件工程师都应该知道的实用技巧。

首先观察你的代码的复杂度。执行需要多长时间完全由这个表达式决定。您已经编写了一个指数 算法，您计算出的值会随着精度 的增加而快速上升。你引用了一个不舒服的数字，8 产生 10^10 或一个进行 100 亿 计算的循环。是的，您注意到了这一点，那时计算机开始需要几秒钟才能产生结果，无论它们有多快。

指数算法不好，它们的性能很差。对于具有阶乘 复杂度的 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.9 万次迭代结果的准确性。

---

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

请注意，在此肘部测试中，能够足够精确地计算加法也非常重要。我故意四舍五入了这些数字，就好像它是在一台能够以 5 位精度执行加法的机器上计算的一样。无论您做什么，结果都不会超过 5 位数。

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

因此，无论您为 presicion 传递什么值，结果都绝不会比 15 位数字更精确。那根本没用，你已经有了精确到 15 位的 pi 值。是数学.Pi

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