如何确定我的pi计算是否准确？

Question

我正在尝试各种方法来实现一个顺序给出pi数字的程序。我尝试了Taylor series方法，但事实证明它收敛得非常慢（当我在一段时间后将我的结果与在线值进行比较时）。无论如何，我正在尝试更好的算法。

因此，在编写程序时，我遇到了问题，就像所有算法一样：我怎么知道我计算的n数字是准确的？

Answer 1

由于我是目前pi数字最多的世界纪录保持者，我将添加我的two cents：

除非您实际设置新的世界记录，否则通常的做法是仅根据已知值验证计算的数字。所以这很简单。

事实上，我有一个网页列出了数字片段，目的是验证对它们的计算：http://www.numberworld.org/digits/Pi/

但是当你进入世界纪录领域时，没有什么可比的。

从历史上看，验证计算数字是否正确的标准方法是使用第二种算法重新计算数字。因此，如果任一计算变坏，则末尾的数字将不匹配。

这通常会使所需时间增加一倍以上（因为第二种算法通常较慢）。但是，一旦你徘徊在未经计算的数字和新的世界纪录的未知领域，这是验证计算数字的唯一方法。

回到超级计算机设置记录的日子里，常用两种不同的AGM algorithms：

这些都是O(N log(N)^2)算法，相当容易实现。

然而，如今，事情有点不同。在最后三个世界记录中，我们使用最快的已知公式（Chudnovsky Formula）执行了一次计算，而不是执行两次计算：

该算法难以实现，但它比AGM算法快得多。

然后我们使用BBP formulas for digit extraction验证二进制数字。

此公式允许您计算任意二进制数字而不计算它之前的所有数字。因此它用于验证最后几个计算的二进制数字。因此它比完整计算快得多。

这样做的好处是：

缺点是：

我已经掩盖了为什么验证最后几位数意味着所有数字都正确的一些细节。但很容易看到这一点，因为任何计算错误都会传播到最后的数字。

现在最后一步（验证转换）实际上非常重要。之前的世界纪录保持者之一实际上已经打电话给我们，因为最初我没有充分描述它是如何运作的。

所以我从我的博客中提取了这个片段：

N = # of decimal digits desired
p = 64-bit prime number

使用基数10算术计算A，使用二进制算术计算B.

如果A = B，那么“极高概率”，转换是正确的。

如需进一步阅读，请参阅我的博客文章Pi - 5 Trillion Digits。

Answer 2

毫无疑问，出于您的目的（我假设只是一项编程练习），最好的办法是检查您的结果是否与网络上pi的任何数字列表相对应。

我们怎么知道那些价值是正确的？好吧，我可以说有计算机科学的方法可以证明算法的实现是正确的。

更务实的是，如果不同的人使用不同的算法，并且他们都同意（选择一个数字）千位（百万，无论如何）小数位，这应该给你一种温暖的模糊感觉，他们做对了。

从历史上看，William Shanks在1873年将pi发布到小数点后707位。可怜的家伙，他从小数点后第528位开始犯了一个错误。

非常有趣的是，1995年an algorithm was published有了直接计算pi的第n位（16位）的属性而无需计算所有之前的数字！

最后，我希望你的初始算法不是pi/4 = 1 - 1/3 + 1/5 - 1/7 + ...这可能是最简单的编程，但它也是最慢的方法之一。查看the pi article on Wikipedia以获得更快的方法。

Answer 3

您可以使用多种方法，看看它们是否收敛到相同的答案。或者从网上抓一些。 Chudnovsky算法通常用作计算pi的非常快速的方法。 http://www.craig-wood.com/nick/articles/pi-chudnovsky/

Answer 4

泰勒系列是一种近似pi的方法。如上所述，它收敛缓慢。

泰勒级数的部分和可以显示在下一个项的某个乘数内，远离pi的真值。

其他近似pi的方法有类似的方法来计算最大误差。

我们知道这一点，因为我们可以用数学证明它。

Answer 5

您可以尝试使用（相当）快速收敛的sin和cos幂级数计算sin(pi/2)（或cos(pi/2)）。（甚至更好：使用各种加倍公式来计算更接近的x=0以获得更快的收敛。）

顺便说一句，比使用tan(x)系列更好的是，计算上说cos(x)是一个黑盒子（例如你可以使用上面的泰勒系列）是通过牛顿进行根发现。当然有更好的算法，但如果你不想验证大量的数字，这应该足够了（实现并不是那么棘手，你只需要一些微积分来理解它的工作原理。）