Welcome to OGeek Q&A Community for programmer and developer-Open, Learning and Share
Welcome To Ask or Share your Answers For Others

Categories

0 votes
392 views
in Technique[技术] by (71.8m points)

algorithm - 如何确定我的pi计算是否准确?(How do I determine whether my calculation of pi is accurate?)

I was trying various methods to implement a program that gives the digits of pi sequentially.

(我正在尝试各种方法来实现一个顺序给出pi数字的程序。)

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?

(因此,在编写程序时,我遇到了问题,就像所有算法一样:我怎么知道我计算的n位数是准确的?)

  ask by Ishan Sharma translate from so

与恶龙缠斗过久,自身亦成为恶龙;凝视深渊过久,深渊将回以凝视…
Welcome To Ask or Share your Answers For Others

1 Reply

0 votes
by (71.8m points)

Since I'm the current world record holder for the most digits of pi, I'll add my two cents :

(由于我是目前pi数字最多的世界纪录保持者,我将加上我的两分钱 :)

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/

(实际上,我有一个网页列出了数字片段,目的是验证对它们的计算: 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:

(在超级计算机设置记录的日子里,常用两种不同的AGM算法 :)

These are both O(N log(N)^2) algorithms that were fairly easy to implement.

(这些都是O(N log(N)^2)算法,相当容易实现。)

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 ):

(在最后三个世界纪录中,我们使用最快的已知公式( Chudnovsky公式 )执行了一次计算,而不是执行两次计算:)

在此输入图像描述

This algorithm is much harder to implement, but it is a lot faster than the AGM algorithms.

(该算法难以实现,但它比AGM算法快得多。)

Then we verify the binary digits using the BBP formulas for digit extraction .

(然后我们使用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.

(因此,这是不是一个完整的运算速度要快得多 。)

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.

    (需要实施Bailey-Borwein-Plouffe (BBP)公式。)

  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.

(使用基数10算术计算A,使用二进制算术计算B.)

在此输入图像描述

If A = B , then with "extremely high probability", the conversion is correct.

(如果A = B ,则“极高概率”,转换是正确的。)


For further reading, see my blog post Pi - 5 Trillion Digits .

(如需进一步阅读,请参阅我的博客文章Pi - 5 Trillion Digits 。)


与恶龙缠斗过久,自身亦成为恶龙;凝视深渊过久,深渊将回以凝视…
OGeek|极客中国-欢迎来到极客的世界,一个免费开放的程序员编程交流平台!开放,进步,分享!让技术改变生活,让极客改变未来! Welcome to OGeek Q&A Community for programmer and developer-Open, Learning and Share
Click Here to Ask a Question

...