我正在尝试各种方法来实现一个按顺序给出 pi 数字的程序。我尝试了泰勒级数方法，但事实证明它的收敛速度非常慢（当我在一段时间后将我的结果与在线值进行比较时）。无论如何，我正在尝试更好的算法。
所以，在编写程序时，我遇到了一个问题，就像所有算法一样：我怎么知道n我计算的数字是准确的？
问问题
122168 次
6 回答
1645
由于我是目前 pi 位数最多的世界纪录保持者，我将加两分钱：
除非您实际上是在设置新的世界纪录，否则通常的做法是根据已知值验证计算出的数字。所以这很简单。
事实上，我有一个网页列出了数字片段，以验证对它们的计算：http ://www.numberworld.org/digits/Pi/
但是当你进入世界纪录领域时，没有什么可以比较的。
从历史上看，验证计算数字是否正确的标准方法是使用第二种算法重新计算数字。因此，如果任一计算出错，最后的数字将不匹配。
这通常是所需时间的两倍多（因为第二种算法通常较慢）。但这是验证计算数字的唯一方法，一旦您进入了从未计算过的数字和新的世界纪录的未知领域。
在超级计算机创造记录的时代，通常使用两种不同的AGM 算法：
这两种O(N log(N)^2)算法都相当容易实现。
然而，如今，情况有些不同了。在最近的三项世界纪录中，我们没有进行两次计算，而是使用已知最快的公式（楚德诺夫斯基公式）只进行了一次计算：
这个算法实现起来要困难得多，但它比 AGM 算法快得多。
然后我们使用BBP 数字提取公式验证二进制数字。
此公式允许您计算任意二进制数字，而无需计算它之前的所有数字。所以它用于验证最后几个计算的二进制数字。因此它比完整计算快得多。
这样做的好处是：
- 只需要一次昂贵的计算。
缺点是：
- 需要实现Bailey-Borwein-Plouffe (BBP) 公式。
- 需要一个额外的步骤来验证从二进制到十进制的基数转换。
我已经掩盖了为什么验证最后几位数字意味着所有数字都是正确的一些细节。但很容易看出这一点，因为任何计算错误都会传播到最后一位。
现在这最后一步（验证转换）实际上相当重要。之前的世界纪录保持者之一实际上呼吁我们这样做，因为最初，我没有充分描述它是如何工作的。
所以我从我的博客中提取了这个片段：
N = # of decimal digits desired
p = 64-bit prime number
使用以 10 为底的算术计算 A，使用二进制算术计算 B。
如果A = B，则以“极高的概率”，转换是正确的。
如需进一步阅读，请参阅我的博文Pi - 5 Trillion Digits。
于 2013-01-11T17:28:04.953 回答
48
毫无疑问，为了您的目的（我假设这只是一个编程练习），最好的办法是对照网络上的任何 pi 数字列表检查您的结果。
我们怎么知道这些值是正确的？好吧，我可以说有计算机科学的方法来证明算法的实现是正确的。
更务实的是，如果不同的人使用不同的算法，并且他们都同意（选择一个数字）一千（百万，等等）小数位，那应该会给你一种温暖的模糊感觉，他们做对了。
从历史上看，William Shanks 在 1873 年将 pi 发布到小数点后 707 位。可怜的家伙，他从小数点后第 528 位开始犯了一个错误。
非常有趣的是，在 1995年发布了一种算法，该算法具有直接计算 pi 的第 n 位（以 16 为底）而无需计算所有前面的数字的特性！
最后，我希望你的初始算法不是pi/4 = 1 - 1/3 + 1/5 - 1/7 + ...那可能是最简单的编程方法，但它也是最慢的方法之一。查看Wikipedia 上的 pi 文章以获得更快的方法。
于 2013-01-11T17:44:23.057 回答
21
您可以使用多种方法，看看它们是否会收敛到相同的答案。或者从网上抢一些。Chudnovsky 算法通常用作计算 pi 的一种非常快速的方法。http://www.craig-wood.com/nick/articles/pi-chudnovsky/
于 2013-01-11T17:21:57.883 回答
15
泰勒级数是近似 pi 的一种方法。如前所述，它收敛缓慢。
泰勒级数的部分和可以显示在下一项的某个乘数内，远离 pi 的真实值。
其他近似 pi 的方法有类似的方法来计算最大误差。
我们知道这一点，因为我们可以在数学上证明它。
于 2013-01-11T17:24:55.493 回答
5
您可以尝试使用（相当）快速收敛的 sin 和 cos 幂级数来计算sin(pi/2)（或就此而言）。cos(pi/2)（更好的是：使用各种加倍公式来计算更接近x=0以更快地收敛。）
顺便说一句，比使用系列更好的tan(x)是，将计算说cos(x)成一个黑匣子（例如，您可以使用上面的泰勒级数）是通过牛顿进行根查找。当然有更好的算法，但是如果你不想验证大量的数字，这就足够了（而且实现起来并不那么棘手，你只需要一点微积分就可以理解它为什么起作用。）
于 2013-01-13T19:09:22.653 回答
0
有一种用于对 arctan 进行逐位评估的算法，只是为了回答这个问题，pi = 4 arctan 1 :)
于 2021-03-20T12:41:13.767 回答