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

我正在尝试各种方法来实现一个程序,依次给出pi的数字。 我尝试了泰勒级数方法,但是它certificate了收敛速度非常慢(当我比较我的结果和在线值之后)。 无论如何,我正在尝试更好的algorithm。

所以,在编写程序时,我遇到了一个问题,就像所有的algorithm一样:我怎么知道我计算的n数字是准确的?

由于我是目前世界logging最多的pi的数字,我会增加我的两分钱 :

除非你真的创造了一个新的世界logging,否则通常的做法就是根据已知的值来validation计算的数字。 所以这很简单。

实际上,我有一个网页列出了一些数字片段,用于validation对他们的计算: http : //www.numberworld.org/digits/Pi/


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

从历史上看,validation计算数字是否正确的标准方法是使用第二种algorithm重新计算数字。 所以如果任何一个计算结果不好,最后的数字将不匹配。

这通常是所需时间的两倍以上(因为第二种algorithm通常较慢)。 但是,只有这样才能validation计算出的数字,一旦你进入未曾计算的数字和新的世界纪录的未知领域。


回到超级计算机设置logging的日子,通常使用两种不同的AGMalgorithm :

  • Gauss-Legendrealgorithm
  • Borwein的algorithm

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

但是,现在事情有点不一样了。 在最近的三次世界logging中,我们不是用两次计算,而是用最快的已知公式( Chudnovsky公式 )进行一次计算:

在这里输入图像说明

这个algorithm实现起来比较困难,但比AGMalgorithm快得多。

然后我们使用BBP公式validation数字提取的二进制数字。

在这里输入图像说明

这个公式允许你计算任意的二进制数字而不需要计算它之前的所有数字。 所以它被用来validation最后几个计算的二进制数字。 因此它比完整的计算快得多。

这样做的好处是:

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

缺点是:

  1. Bailey-Borwein-Plouffe (BBP)配方的实施是必要的。
  2. validation从二进制到十进制的基数转换需要额外的步骤。

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


现在最后一步(validation转换)实际上相当重要。 以前的世界纪录保持者之一实际上就是这样叫我们的,因为最初我没有给出足够的描述。

所以我从我的博客上摘下了这个片段:

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

在这里输入图像说明

用二进制algorithm计算一个使用base 10algorithm和B。

在这里输入图像说明

如果A = B ,那么以“非常高的概率”,转换是正确的。


有关进一步阅读,请参阅我的博客文章Pi – 5 Trillion Digits

毫无疑问,为了您的目的(我认为这只是一个编程练习),最好的办法是检查您的结果与networking上的任何pi数字列表。

我们怎么知道这些值是正确的? 那么,我可以说,有计算机科学方法来certificatealgorithm的实现是正确的。

更实际的是,如果不同的人使用不同的algorithm,他们都同意(select一个数字)一千(百万,无论)小数位,这应该给你一个温暖的模糊的感觉,他们是正确的。

从历史上看,William Shanks在1873年把pi发布到了707个小数位。可怜的人,他在小数点后第五十二个位置开了一个错误。

非常有趣的是,在1995 年发布了一个algorithm , 该algorithm具有直接计算pi的第n个数字(基数为16) 而不必计算所有前面的数字的属性!

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

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

泰勒级数是一个近似pi的方法。 如前所述,它收敛缓慢。

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

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

我们知道这一点,因为我们可以在math上certificate这一点。

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

顺便说一句,比使用tan(x)系列更好的是,将cos(x)计算为黑盒子(例如,你可以使用泰勒级数)就是通过牛顿进行寻根。 那里肯定有更好的algorithm,但是如果你不想validation大量的数字,这应该就足够了(实现起来并不那么棘手,你只需要一些微积分来理解它为什么起作用)。