如何确定我对 pi 的计算是否准确? [英] How do I determine whether my calculation of pi is accurate?

问题描述

我尝试了各种方法来实现一个按顺序给出 pi 数字的程序.我尝试了

这个算法实现起来要困难得多，但比 AGM 算法快得多.

然后我们使用

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

这样做的好处是:

1. 只需要一个昂贵的计算.

缺点是:

1. 使用基数为 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:

   • Gauss–Legendre algorithm
   • Borwein's algorithm

   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:

   1. Only one expensive computation is needed.

   The disadvantage is:

   1. An implementation of the Bailey–Borwein–Plouffe (BBP) formula is needed.
   2. 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屋！