如何确定我的pi计算是否准确？
Ish*_*rma 765 language-agnostic algorithm math pi
我正在尝试各种方法来实现一个顺序给出pi数字的程序.我尝试了泰勒系列方法,但事实证明它非常缓慢地收敛(当我在一段时间后将我的结果与在线值进行比较时).无论如何,我正在尝试更好的算法.
因此,在编写程序时,我遇到了问题,就像所有算法一样:我怎么知道n我计算的数字是准确的？
Mys*_*ial 1621
由于我是目前pi数字最多的世界纪录保持者,我将加上我的两分钱:
除非您实际设置新的世界记录,否则通常的做法是仅根据已知值验证计算的数字.所以这很简单.
事实上,我有一个网页列出了数字片段,目的是验证对它们的计算:http://www.numberworld.org/digits/Pi/
但是当你进入世界纪录领域时,没有什么可比的.
从历史上看,验证计算数字是否正确的标准方法是使用第二种算法重新计算数字.因此,如果任一计算变坏,则末尾的数字将不匹配.
这通常会使所需时间增加一倍以上(因为第二种算法通常较慢).但是,一旦你徘徊在未经计算的数字和新的世界纪录的未知领域,这是验证计算数字的唯一方法.
在超级计算机设置记录的日子里,常用两种不同的AGM算法:
这些都是O(N log(N)^2)相当容易实现的算法.
然而,如今,事情有点不同.在最后三个世界纪录中,我们使用最快的已知公式(Chudnovsky公式)执行了一次计算,而不是执行两次计算:
该算法难以实现,但它比AGM算法快得多.
此公式允许您计算任意二进制数字而不计算它之前的所有数字.因此它用于验证最后几个计算的二进制数字.因此,这是很多比一个完整的计算速度更快.
这样做的好处是:
- 只需要一个昂贵的计算.
缺点是:
- 需要实施Bailey-Borwein-Plouffe(BBP)公式.
- 需要额外的步骤来验证从二进制到十进制的基数转换.
我已经掩盖了为什么验证最后几位数意味着所有数字都正确的一些细节.但很容易看到这一点,因为任何计算错误都会传播到最后的数字.
现在最后一步(验证转换)实际上非常重要.之前的世界纪录保持者之一实际上已经打电话给我们,因为最初我没有充分描述它是如何运作的.
所以我从我的博客中提取了这个片段:
N = # of decimal digits desired
p = 64-bit prime number
使用基数10算术计算A,使用二进制算术计算B.
如果A = B,那么"极高概率",转换是正确的.
如需进一步阅读,请参阅我的博客文章Pi - 5 Trillion Digits.
- @FunsukWangadu我只能为自己说话,但就在这里:我从未真正关心过Pi本身.对我来说,这只是另一个数字.该值不是数字本身或10兆字节的无用数字,它是用于实现它的*方法*.几个世纪的数学,以及数十年促成这一壮举的计算机/编程研究都适用于许多其他领域,因此比数字硬盘驱动器更有价值.简单地说:计算Pi的数字更像是一项运动. (82认同)
- 是的,Chudnovsky的公式每学期收敛14.18位数.因此,您可以将总位数除以该位数,以获得所需的术语数量.(确切值是:`Log(151931373056000)/ Log(10)= 14.181647462725477655 ...`) (21认同)
- 并回答关于如何知道特定算法何时收敛到N个数字的另一个问题:这要求您知道算法的收敛行为."ArcTan(1)"的泰勒级数是对数收敛的.所以你需要指数大量的术语来收敛 - 简而言之,不要使用它. (15认同)
- @Mystical,从另一个[stackoverflow问题]偶然发现你的Pi计算网站(http://stackoverflow.com/questions/11227809/why-is-processing-a-sorted-array-faster-than-an-unsorted-array并且忍不住对你们所做的事情嗤之以鼻.喜欢日志中的硬盘故障/地震:)真是太棒了! (8认同)
- @ erikb85有点儿.BBP公式(在某种程度上)计为第二种算法.但是它本身还不够,因为它没有验证到基数10的转换.使用BBP +转换检查来消除对第二次计算的需要的想法不是我的.这是Fabrice Bellard在2009年的世界纪录中首次完成的.这是一个好主意,我们做了同样的事情并对其进行了改进. (7认同)
- @SuperPrograman直到去年12月左右,我才能通过bittorrent下载前5万亿个数字.但是自从我离开学校以来,我不再有带宽来播种它.所以我只能处理特定偏移量的少量数字请求.有几个重量级的数学家让我对运行数字统计感兴趣.他们最终给了我一个我在本地跑的程序. (4认同)
- @ user3576467如果结果不匹配,则表示硬件,软件或实现中存在错误.这不是公式中的错误,因为公式已经在数学上证明是正确的.因此,如果结果不匹配,它将成为一个史诗般的调试问题.幸运的是,由于有许多旨在尽早发现错误的保护措施,因此尚未实施. (3认同)
小智 48
毫无疑问,出于您的目的(我假设它只是一项编程练习),最好的办法是检查您的结果是否与网络上pi的任何数字列表相对应.
我们怎么知道那些价值是正确的？好吧,我可以说有计算机科学的方法可以证明算法的实现是正确的.
更实际的是,如果不同的人使用不同的算法,并且他们都同意(选择一个数字)千位(百万,无论如何)小数位,这应该给你一种温暖的模糊感觉,他们做对了.
从历史上看,William Shanks在1873年将pi发布到小数点后707位.可怜的家伙,他从小数点后第528位开始犯了一个错误.
非常有趣的是,在1995 年发布了一种算法,该算法具有直接计算pi的第n位(基数16)而不必计算所有先前数字的属性!
最后,我希望你的初始算法不是pi/4 = 1 - 1/3 + 1/5 - 1/7 + ...最简单的编程,但它也是最慢的方法之一.查看维基百科上的pi文章,了解更快的方法.
- 最后一个公式(Leibniz公式,iirc)实际上是加法和减法的交替. (7认同)
arg*_*age 21
您可以使用多种方法,看看它们是否收敛到相同的答案.或者从网上抓一些.Chudnovsky算法通常用作计算pi的非常快速的方法.http://www.craig-wood.com/nick/articles/pi-chudnovsky/
- @IshanSharma如果这两个算法是独立的,那么相同结果的两个计算错误的可能性几乎为零.如果计算中出现任何问题,最终结果将不匹配 - 因此您至少知道其中一个是错误的. (7认同)
Yak*_*ont 15
泰勒系列是一种近似pi的方法.如上所述,它收敛缓慢.
泰勒级数的部分和可以显示在下一个项的某个乘数内,远离pi的真值.
其他近似pi的方法有类似的方法来计算最大误差.
我们知道这一点,因为我们可以用数学证明它.
- 借调了。我认为这里的大多数答案都没有对“数学证明”的概念给予足够的重视。无论您的程序用于计算 pi 的数字，它永远不会比最令人信服的数学证明更令人信服，证明您的程序的方法确实计算 pi。这表明对 pi 计算 pi 的程序有一个不同的限制：它们应该像性能和正确性一样追求“可理解性”。 (2认同)
小智 5
您可以尝试使用（相当）快速收敛的正弦和余弦幂级数来计算sin(pi/2)（或cos(pi/2)就此而言）。（甚至更好：使用各种加倍公式来计算更接近的值，x=0以加快收敛速度。）
顺便说一句，比起使用序列而言，更好的tan(x)是，通过计算可以说cos(x)是一个黑匣子（例如，您可以使用上述的taylor序列）是通过牛顿进行寻根。当然那里有更好的算法，但是如果您不想验证大量数字，这就足够了（并且实现起来并不是那么棘手，并且您只需要一点微积分就可以理解它的工作原理。）
- 我想并不是每个人都可以很清楚地评估`sin（x）`和`cos（x）`实际上比计算Pi本身困难得多。 (15认同)
- 我不太清楚这将如何帮助发现第1000个数字减1。您需要非常精确的`sin（pi / 2）`值吗？ (6认同)
- 出于明显的原因，您不应为此使用sin（pi / 2）。最好改用sin（pi / 6）并确保它精确地等于1/2。 (2认同)
| 归档时间： |
|
| 查看次数： |
118290 次 |
| 最近记录： |