如何确定我的π计算结果的准确性？

Question

如何确定我的π计算结果的准确性？

algorithmmathlanguage-agnosticpi

793

我一直在尝试各种方法来实现一个按顺序给出π的各个数字的程序。我试过泰勒级数法，但它收敛得非常慢（当我将我的计算结果与网上的值进行比较后）。不管怎样，我正在尝试更好的算法。

因此，在编写程序时，我遇到了一个问题，就像所有算法一样：我如何知道我计算出的前n位数字是准确的？

- Ishan Sharma

23

更多是一个数学问题。优秀的算法还会提供误差估计。 - example

38

与 pi 进行比较？ - Dave Newton

55

“Literally everywhere” 可以翻译为“到处都是”或者“无处不在”。 - Lightness Races in Orbit

33

我可以帮您检查到3.141592653589793238462643383279502，超过这个范围，为什么您需要这么多位数呢？（这就像用一个宇宙大小的圆来达到原子级别的精度。） - AJ Henderson

69

你为什么不试着除以圆周率，看看结果是否为1呢？（开玩笑的） - user541686

显示剩余10条评论

6个回答

50

毫无疑问，对于您的目的（我假设这只是一个编程练习），最好的方法是与网络上任何一个圆周率数字清单进行比较检查结果。

那我们如何知道这些值是正确的呢？嗯，我可以说，有计算机科学的方法来证明算法实现是正确的。

更实际地说，如果不同的人使用不同的算法，并且他们都同意到（选一个数字）一千（一百万，任何一个）小数位，这应该让你感觉很舒服，他们得到了正确答案。

历史上，William Shanks在1873年将pi推算到707位小数。可怜的家伙，在第528个小数位就出错了。

非常有趣的是，在1995年发表了一篇算法，它具有直接计算pi的第n位（以16进制为基数）而无需计算所有先前数字的属性！

最后，我希望您的初始算法不是pi/4 = 1 - 1/3 + 1/5 - 1/7 + ...。虽然这可能是最简单的编程方法，但也是最慢的方法之一。请参阅维基百科上关于圆周率更快的方法。

- Larry Smith

7

那个公式（我记得是莱布尼兹公式）实际上交替使用加法和减法。 - Thomas

21

您可以采用多种方法来查看它们是否收敛到相同的答案。或者从网络上获取一些方法。 Chudnovsky算法通常用作计算π的非常快速的方法。

http://www.craig-wood.com/nick/articles/pi-chudnovsky/

- argentage

虽然采用多种方法可以降低风险，但我仍然不能确定两种方法都是错误的情况。在网络上查找并不具有可靠性，那为什么不直接从网络上获取数值呢？我正在考虑使用bbp算法，哪个更适合呢？ - Ishan Sharma

8

如果这两个算法是独立的，那么它们计算出完全相同的错误结果的概率几乎为零。如果其中任何一个计算出现问题，最终的结果将不匹配 - 所以你知道它们中至少有一个是错误的。 - Mysticial

15

Taylor级数是近似π的一种方法。如注所述，它收敛缓慢。

Taylor级数的部分和可被证明在某个倍数范围内接近π的真实值，与下一个项之间的误差也相应较小。

其他求近似π的方法也有类似的计算最大误差的方式。

我们之所以知道这个，是因为我们可以在数学上证明它。

- Yakk - Adam Nevraumont

2

同意。我认为这里的大部分答案都没有足够强调“数学证明”的概念。无论你的程序计算π的数字是什么，它永远不会比你的程序方法确实计算π的最有说服力的数学证明更有说服力。这表明了计算π的程序的不同约束：它们应该在性能和正确性之外也要追求可理解性。 - Luis Casillas

5

您可以尝试使用（相当）快速收敛的正弦和余弦幂级数计算sin(pi/2)（或cos(pi/2)）。（更好的方法是使用各种加倍公式来计算更靠近x=0，以实现更快的收敛效果。）顺便说一句，比使用tan(x)级数更好的方法是，将计算cos(x)作为黑匣子（例如，您可以像上面那样使用泰勒级数），然后通过牛顿法进行根查找。虽然肯定有更好的算法，但如果您不想验证大量位数，这应该就足够了（而且它并不那么棘手，您只需要一点微积分知识就可以理解它为什么有效）。

- user1974703

7

我不太明白它如何帮助发现第1000位数字偏离1。你需要非常精确的值来计算 sin(pi/2)，对吧？ - Matthieu M.

我不确定如何评价之前的答案，除非它是一个玩笑或者什么的。sin(pi/2) = 1 cos(pi/2) = 0 所以，我会说这些确实收敛得很快。 - BentFranklin

17

我猜不是每个人都明白，精确计算sin(x)和cos(x)比计算π本身要困难得多。 - Mysticial

2

由于明显的原因，你不应该使用sin(pi/2)。最好改用sin(pi/6)，并确保其结果恰好为1/2。 - Robert Lozyniak

1

有一种算法可以逐位计算arctan，只是为了回答这个问题，pi = 4 arctan 1 :)

- Sam Ginrich

有人对此进行了负面评价，可能是因为他们没有理解“按顺序列出圆周率的数字”的任务。 - Sam Ginrich

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Mysticial · Accepted Answer

作为当前最多圆周率位数的世界纪录保持者，我想要发表一下我的个人观点：

除非你真的在打破世界纪录，通常的做法就是将计算出来的数字与已知值进行验证。所以这很简单。

实际上，我有一个网页，列出了一些圆周率位数的片段，用于验证计算结果：http://www.numberworld.org/digits/Pi/

但是当你进入世界纪录领域时，就没有什么可比性了。

历史上，验证计算出的数字正确性的标准方法是使用第二个算法重新计算数字。因此，如果任何一个计算出现问题，最后的数字将不匹配。

这通常会增加所需时间的两倍以上（因为第二个算法通常更慢）。但这是在你进入从未计算过的数字和新的世界记录的未知领域后验证计算数字的唯一方法。

在超级计算机创造记录的时代，通常使用两种不同的AGM算法：

这两种算法都是O(N log(N)^2)算法，实现起来相对容易。

然而，现在情况有所不同。在过去三次世界纪录中，我们没有执行两次计算，而是使用已知最快公式（Chudnovsky公式）只进行了一次计算：

这个算法难以实现，但比AGM算法快得多。

然后，我们使用BBP公式进行数字提取来验证二进制位。

这个公式允许你计算任意二进制位数，而不需要计算它之前的所有位数。因此，它用于验证最后几个计算的二进制位数。因此，它比完整计算快得多。

其中的优点是：

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

缺点是：

1. 需要实现Bailey–Borwein–Plouffe（BBP）公式。 2. 需要额外的步骤来验证从二进制到十进制的基数转换。 _{我略过了一些细节，解释为什么验证最后几位数字意味着所有数字都是正确的。但很容易看出这一点，因为任何计算错误都会传播到最后的数字。}

现在这最后一步（验证转换）实际上非常重要。之前的世界纪录保持者曾经指责我们，因为起初我没有足够描述它是如何工作的。

所以我从我的博客中提取了这段代码：

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

使用十进制算法计算A，使用二进制算法计算B。

如果 A = B，那么 "极高的概率" 下，转换是正确的。

如需进一步阅读，请查看我的博客文章圆周率- 5万亿位数。