[algorithm] How do I determine whether my calculation of pi is 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:

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

Enter image description here

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.

Enter image description here

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

Enter image description here

Compute A using base 10 arithmetic and B using binary arithmetic.

Enter image description here

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


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

Examples related to algorithm

How can I tell if an algorithm is efficient? Find the smallest positive integer that does not occur in a given sequence Efficiently getting all divisors of a given number Peak signal detection in realtime timeseries data What is the optimal algorithm for the game 2048? How can I sort a std::map first by value, then by key? Finding square root without using sqrt function? Fastest way to flatten / un-flatten nested JSON objects Mergesort with Python Find common substring between two strings

Examples related to math

How to do perspective fixing? How to pad a string with leading zeros in Python 3 How can I use "e" (Euler's number) and power operation in python 2.7 numpy max vs amax vs maximum Efficiently getting all divisors of a given number Using atan2 to find angle between two vectors How to calculate percentage when old value is ZERO Finding square root without using sqrt function? Exponentiation in Python - should I prefer ** operator instead of math.pow and math.sqrt? How do I get the total number of unique pairs of a set in the database?

Examples related to language-agnostic

IOException: The process cannot access the file 'file path' because it is being used by another process Peak signal detection in realtime timeseries data Match linebreaks - \n or \r\n? Simple way to understand Encapsulation and Abstraction How can I pair socks from a pile efficiently? How do I determine whether my calculation of pi is accurate? What is ADT? (Abstract Data Type) How to explain callbacks in plain english? How are they different from calling one function from another function? Ukkonen's suffix tree algorithm in plain English Private vs Protected - Visibility Good-Practice Concern

Examples related to pi

Java and unlimited decimal places? How do I determine whether my calculation of pi is accurate? Should I use scipy.pi, numpy.pi, or math.pi? how to use math.pi in java How to printf long long