我正在尝试各种方法来实现一个顺序给出pi数字的程序 . 我尝试了Taylor series方法,但事实证明它收敛得非常慢(当我在一段时间后将结果与在线值进行比较时) . 无论如何,我正在尝试更好的算法 .
因此,在编写程序时,我遇到了问题,就像所有算法一样:我怎么知道我计算的 n
数字是准确的?
我正在尝试各种方法来实现一个顺序给出pi数字的程序 . 我尝试了Taylor series方法,但事实证明它收敛得非常慢(当我在一段时间后将结果与在线值进行比较时) . 无论如何,我正在尝试更好的算法 .
因此,在编写程序时,我遇到了问题,就像所有算法一样:我怎么知道我计算的 n
数字是准确的?
5 回答
泰勒系列是一种近似pi的方法 . 如上所述,它收敛缓慢 .
泰勒级数的部分和可以显示在下一个项的某个乘数内,远离pi的真值 .
其他近似pi的方法有类似的方法来计算最大误差 .
我们知道这一点,因为我们可以用数学证明它 .
毫无疑问,出于您的目的(我假设它只是一项编程练习),最好的办法是检查您的结果是否与网络上pi的任何数字列表相对应 .
我们怎么知道那些 Value 是正确的?好吧,我可以说有计算机科学的方法可以证明算法的实现是正确的 .
更实际的是,如果不同的人使用不同的算法,并且他们都同意(选择一个数字)千位(百万,无论如何)小数位,这应该给你一种温暖的模糊感觉,他们做对了 .
从历史上看,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以获得更快的方法 .您可以使用多种方法,看看它们是否会收敛到相同的答案 . 或者从网上抓一些 . Chudnovsky算法通常用作计算pi的非常快速的方法 . http://www.craig-wood.com/nick/articles/pi-chudnovsky/
自从'm the current world record holder for the most digits of pi, I' ll添加我的two cents:
除非您实际设置新的世界记录,否则通常的做法是仅根据已知值验证计算的数字 . 这很简单 .
事实上,我有一个网页列出了数字片段,目的是验证对它们的计算:http://www.numberworld.org/digits/Pi/
但是当你进入世界纪录领域时,没有什么可比的 .
历史上,验证计算数字是否正确的标准方法是使用第二算法重新计算数字 . 因此,如果任一计算变坏,则末尾的数字将不匹配 .
这通常会使所需时间增加一倍以上(因为第二种算法通常较慢) . 但是,一旦你徘徊在未经计算的数字和新的世界纪录的未知领域,这是验证计算数字的唯一方法 .
回到超级计算机设置记录的日子里,常用了两种不同的AGM algorithms:
Gauss–Legendre algorithm
Borwein's algorithm
这些都是
O(N log(N)^2)
算法,相当容易实现 .然而,如今,事情有点不同 . 在最后三个世界记录中,我们使用最快的已知公式(Chudnovsky Formula)执行了一次计算,而不是执行两次计算:
该算法难以实现,但它比AGM算法快得多 .
然后我们使用BBP formulas for digit extraction验证二进制数字 .
此公式允许您计算任意二进制数字而不计算它之前的所有数字 . 因此它用于验证最后几个计算的二进制数字 . 因此它比完整计算快92066_ .
这样做的好处是:
缺点是:
需要实施Bailey–Borwein–Plouffe(BBP)公式 .
需要额外的步骤来验证从二进制到十进制的基数转换 .
我已经掩盖了为什么验证最后几位数意味着所有数字都是正确的一些细节 . 但很容易看到这一点,因为任何计算错误都会传播到最后的数字 .
现在,最后一步(验证转换)实际上非常重要 . 之前的世界纪录保持者之一 actually called us out 因为,最初,我没有充分描述它是如何运作的 .
所以我从我的博客中提取了这个片段:
使用基数10算术计算A,使用二进制算术计算B.
如果是
A = B
,那么使用"extremely high probability",转换是正确的 .如需进一步阅读,请参阅我的博客文章 Pi - 5 Trillion Digits .
您可以尝试使用(相当)快速收敛的sin和cos幂级数来计算
sin(pi/2)
(或cos(pi/2)
) . (甚至更好:使用各种加倍公式来更快地计算更近的x=0
收敛 . )顺便说一句,比使用
tan(x)
系列更好的是,计算说cos(x)
作为一个黑盒子(例如你可以使用上面的泰勒系列)是通过牛顿进行根查找 . 当然有更好的算法,但是如果你没有那么难以实现,你只需要一些微积分来理解它的工作原理 . )