How do I determine whether my calculation of pi is accurate? Ask Question

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.}

さて、この最後のステップ (変換の検証) は、実はかなり重要です。以前の世界記録保持者の 1 人が、当初、私がその仕組みを十分に説明していなかったため、この点について私たちを非難しました。

そこで私は自分のブログからこの抜粋を抜粋しました:

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