algorithm - 如何确定计算pi的精确呢?

  显示原文与译文双语对照的内容

我正在尝试各种方法来实现一个给出圆周率数字的程序。 我尝试了泰勒级数方法,但它收敛得非常缓慢( 在一段时间后将结果与在线值比较) 。 总之,我在尝试更好的算法。

所以,在编写程序时,我遇到了一个问题,如同所有算法: 如何知道我计算的n 位数是准确的?

时间:

因为我是当前世界上最多数字的记录持有者,我将添加我的两个分数:

除非你正在设置一个新的世界记录,通常的做法是根据已知的值验证计算的数字。 这很简单。

事实上,我有一个网页,列出了一些数字 Fragment,用于验证对它们的计算: http://www.numberworld.org/digits/Pi/


但是当你进入world-record领域时,没有什么可以比对。

历史上,验证计算数字正确的标准方法是使用第二个算法重新计算数字。 因此,如果任一计算出错,末尾的数字将不匹配。

这通常会超过( 因为第二个算法通常较慢) 所需时间的两倍。 但这是唯一的方法,验证计算的数字一旦你走进了未知的never-before-computed数字和一个新的世界记录。


回到超级计算机设置记录的日子中,通常使用两种不同的 mep算法:

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

然而,现在,事情有点不同。 在最后三个世界记录中,我们使用最快的已知公式( Chudnovsky公式 ) 只执行了一个计算,而不是执行两个计算:

Enter image description here

这个算法很难实现,但它比算法快得多。

然后我们使用 BBP公式来验证二进制数字。

Enter image description here

这里公式允许你计算任意二进制数字 ,而不需要计算所有数字。 所以它用来验证最后几个计算的二进制数字。 因此它是 多少 快于一个完整的计算。

它的优点是:

  1. 只需要一个昂贵的计算。

缺点是:

  1. 需要 Bailey–Borwein–Plouffe ( BBP ) 公式的实现。
  2. 需要一个额外步骤来验证二进制到十进制的基数转换。

我已经解释了为什么验证最后几个数字意味着所有数字都是正确的。 但是很容易看到这一点,因为任何计算错误都会传播到最后一个数字。


最后一步( 正在验证转换) 实际上相当重要。 完成上述世界纪录持有人 实际上把我们叫出来 在这里,因为,最初,我没有给它做一个充分的说明有奏效。

所以我从我的博客中提取了这个 Fragment:


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

Enter image description here

使用二进制算术计算一个使用 10的算术和。

enter image description here

如果 A = B,则使用"极高的概率",转换是正确的。


要进一步阅读,请参见我的博客文章 π - 5万亿数字

毫无疑问,出于你的目的,最好的方法是根据站点上圆周率的任何列表检查结果。

我们如何知道这些值是正确的? 我可以说有computer-science-y方法来证明算法的实现是正确的。

更在语用上,如果不同的人采用不同的算法,和他们都同意( 选择一个数字) 千(,whatever ) 小数位数,应该可以给你一个温暖的模糊感觉到他们的号码是否准确。

历史上,Shanks将圆周率发布到 707位十进制位置 1873 。 可怜的家伙,他从 528位小数处开始出错。

非常有趣的是,在 1995 一个算法,发表过表示有该属性,该属性会直接计算圆周率的n 个数字( 基础 16 ) ,而不必计算前面所有的数字 !

最后,我希望你的初始算法不是 pi/4 = 1 - 1/3 + 1/5 - 1/7 +.. . 这可能是最简单的程序,但它也是最慢的方法之一。 查看关于维基百科的文章以获得更快的方法。

于sin和cos,可以尝试在计算相关 sin(pi/2) ( 或者 cos(pi/2)的问题) 采用( 相当) 并快速得出电力 series. ( 更好的方法:使用不同的公式来计算更接近的x=0 以加快收敛。)

顺便一提,比系列对于 tan(x) 是效果更好,因为运算说 cos(x) 视为一个黑盒子( 如, 你可以用上面的泰勒级数,通过牛顿做根查找。 确实有更好的算法,但是如果你不想验证大量的数字,这就足够了( 实现它并不难,你只需要一点点微积分来理解它)

...