如何确定我的计算圆周率是否准确？ [英] How to determine whether my calculation of pi is accurate?
问题描述
我尝试各种方法来实施一项计划，使该顺序圆周率的数字。我试过泰勒级数的方法，但事实证明收敛极为缓慢（当我比较我的结果与经过一番网上值时间）。无论如何，我想更好的算法。
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.
因此，在编写程序我被困在一个问题，因为所有的算法：我怎么知道 N ，我已经计算出的数字是准确的？
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.
其实，我有一个网页，列出的数字代码段用于验证对他们计算的目的： HTTP：// WWW .numberworld.org /数字/ PI /
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.
早在天，其中超级计算机进行了设置的记录，两个不同的 AGM算法，常用：
Back in the days where supercomputers were setting the records, two different AGM algorithms were commonly used:
- Gauss–Legendre algorithm
- Borwein's algorithm
这些都是 O（N日志（N）^ 2）那是相当容易实现。算法
These are both O(N log(N)^2) algorithms that were fairly easy to implement.
但是，现在，事情有点不同。而不是执行两种计算在过去的三项世界纪录，我们用最快的著名公式只进行一次计算（ Chudnovsky式 ）：
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):
这个算法是很难实现的，但它比AGM算法快了很多。
This algorithm is much harder to implement, but it is a lot faster than the AGM algorithms.
然后，我们使用 BBP公式，数字提取
这个公式可以计算任意的二进制数字的没有的计算所有的前位。因此它是用来验证最后几个计算二进制数字。因此，这是 多的不是一个完整的运算速度更快。
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.
这样做的优点是：
- 只有一个昂贵的计算是必要的。
的缺点是：
- 的<一个一个实现href="http://en.wikipedia.org/wiki/Bailey%E2%80%93Borwein%E2%80%93Plouffe_formula">Bailey–Borwein–Plouffe （BBP）的公式是必要的。
- 的附加步骤是必要的，以验证从二进制到十进制的基数的转换。
- 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.
<子>我已经掩盖了，为什么核查的最后几个数字的一些细节意味着所有的数字都是正确的。但它很容易地看到这一点，因为任何计算误差将传播到最后一位数字。
现在（验证转换）这最后一步，其实是相当的重要。其中previous的世界纪录保持者的的的居然叫我们出去的这一点，因为，一开始，我并没有给它如何工作的充分说明。
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
计算使用基10算法，并使用二进制算术B点。
Compute A using base 10 arithmetic and B using binary arithmetic.
如果 A = B ，然后用极有可能，转化为正确的。
If A = B, then with "extremely high probability", the conversion is correct.
有关进一步阅读，请参阅我的博客文章 丕 - 5万亿位数
For further reading, see my blog post Pi - 5 Trillion Digits.
这篇关于如何确定我的计算圆周率是否准确？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
