如何确定pi的计算是否正确? [英] How do I determine whether my calculation of pi is accurate?
问题描述
我正在尝试各种方法来实现一个程序，该程序顺序给出pi的数字.我尝试了泰勒级数方法，但事实证明该方法收敛非常慢(当我将结果与一段时间后显示在线值).无论如何，我正在尝试更好的算法.
因此，在编写程序时，就像所有算法一样，我陷入了一个问题:我怎么知道我计算出的n位数字是正确的?
由于我是pi位数最高的当前世界纪录保持者，因此我将添加 http://www.numberworld.org/digits/Pi/
但是，当您进入世界纪录的领土时，没有什么可比拟的了.
从历史上看，用于验证计算出的数字正确的标准方法是使用第二种算法重新计算数字.因此，如果其中任何一项计算出错，则末尾的数字将不匹配.这通常需要两倍以上的时间(因为第二种算法通常较慢).但是，这是在您进入从未计算过的数字和新的世界纪录的未知领域之后，验证已计算数字的唯一方法.
在超级计算机设置记录的年代，通常使用两种不同的 AGM算法 :
这两个都是O(N log(N)^2)算法，很容易实现.
但是，如今情况有所不同.在最近的三个世界记录中，我们没有执行两次计算，而是使用最快的已知公式( Chudnovsky公式):
这种算法很难实现，但比AGM算法要快得多.
然后，我们使用 BBP公式来验证二进制数字用于数字提取.
此公式允许您计算任意二进制数字，而无需计算之前的所有数字.因此，它用于验证最后几个计算出的二进制数字.因此，它比完整计算快 .
这样做的优点是:
- 只需要进行一次昂贵的计算即可.
缺点是:
- Bailey–Borwein–Plouffe (BBP)公式是必需的.
- 需要执行其他步骤来验证基数从二进制到十进制的转换.
我已经详细介绍了为什么验证最后几位数字意味着所有数字都是正确的细节.但这很容易看到，因为任何计算错误都会传播到最后几位.
现在，最后一步(验证转换)实际上非常重要.以前的世界纪录保持者之一 实际上是在叫我们走 ，因为一开始我没有给出足够的描述.
所以我已经从我的博客中提取了以下代码段:
N = # of decimal digits desired
p = 64-bit prime number
使用10为底的算术运算A，使用二进制算术的B运算.
如果为A = B，则概率很高"，则表示转换正确.
有关更多信息，请参阅我的博客文章 Pi-5万亿位数 .
I was trying various methods to implement a program that gives the digits of pi sequentially. I tried the Taylor series method, but it proved to converge extremely slowly (when I compared my result with the online values after some time). Anyway, I am trying better algorithms.
So, while writing the program I got stuck on a problem, as with all algorithms: How do I know that the n digits that I've calculated are accurate?
Since I'm the current world record holder for the most digits of pi, I'll add my two cents:
Unless you're actually setting a new world record, the common practice is just to verify the computed digits against the known values. So that's simple enough.
In fact, I have a webpage that lists snippets of digits for the purpose of verifying computations against them: http://www.numberworld.org/digits/Pi/
But when you get into world-record territory, there's nothing to compare against.
Historically, the standard approach for verifying that computed digits are correct is to recompute the digits using a second algorithm. So if either computation goes bad, the digits at the end won't match.
This does typically more than double the amount of time needed (since the second algorithm is usually slower). But it's the only way to verify the computed digits once you've wandered into the uncharted territory of never-before-computed digits and a new world record.
Back in the days where supercomputers were setting the records, two different AGM algorithms were commonly used:
These are both O(N log(N)^2) algorithms that were fairly easy to implement.
However, nowadays, things are a bit different. In the last three world records, instead of performing two computations, we performed only one computation using the fastest known formula (Chudnovsky Formula):
This algorithm is much harder to implement, but it is a lot faster than the AGM algorithms.
Then we verify the binary digits using the BBP formulas for digit extraction.
This formula allows you to compute arbitrary binary digits without computing all the digits before it. So it is used to verify the last few computed binary digits. Therefore it is much faster than a full computation.
The advantage of this is:
- Only one expensive computation is needed.
The disadvantage is:
- An implementation of the Bailey–Borwein–Plouffe (BBP) formula is needed.
- An additional step is needed to verify the radix conversion from binary to decimal.
I've glossed over some details of why verifying the last few digits implies that all the digits are correct. But it is easy to see this since any computation error will propagate to the last digits.
Now this last step (verifying the conversion) is actually fairly important. One of the previous world record holders actually called us out on this because, initially, I didn't give a sufficient description of how it worked.
So I've pulled this snippet from my blog:
N = # of decimal digits desired
p = 64-bit prime number
Compute A using base 10 arithmetic and B using binary arithmetic.
If A = B, then with "extremely high probability", the conversion is correct.
For further reading, see my blog post Pi - 5 Trillion Digits.
这篇关于如何确定pi的计算是否正确?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
