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

Question

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?

Lysol

more of a mathematical problem. good algorithms also give an estimate of the error. – Plebiscite

The value of pi is available literally everywhere. Use multiple sources that match to be sure it's right. I once saw a "1000 digits of pi" website that was completely wrong. – Splendent

Use the Spigot algorithm. After step n, the error will be less than 1/16^n. The original paper contains a proof of why this converges to pi. – Plebiscite

Compare against pi? – Celandine

@chris: "Literally everywhere"? – Alejandrinaalejandro

@LightnessRacesinOrbit, So I exaggerated a little bit. For what I meant, look at this. It's insane how many different sites feature digits of pi, and if you can't count on any of them, you know it's time for Mysticial's answer. Of course, Mysticial's site is pretty reliable ;) – Splendent

@Mr.Mindor - There's no need to obfuscate the issue, just as there's no need to be afraid of fractions. – Conspectus

I can check for you up to 3.141592653589793238462643383279502, beyond that, why do you need such a big number of digits? (That's something like atomic level accuracy with a circle the size of the universe.) – Dagoba

@Splendent "a little bit"... hmm... 25,270,000,000 results vs 1,950,000 results. – Loewi

This seems like more of a philosophical problem than mathematical. As you said, this question can apply to any algorithm, but it's even more general than that. How do we know that anything we believe is true? The scientific method doesn't actually prove anything in the mathematical sense, it merely provides confirmation that strengthens believe. And even mathematical proofs depend on the truth of the axioms of the system and logical algebra. Read GEB to see how this is a reductio ad infinitum. – Ranunculaceous

Why don't you just divide by pi and check if the result is 1? (just kidding) – King

@AJHenderson higher-precision PI might be used for mathematical purposes. – Oz

@AJHenderson, finding a really big number of digits of pi is a standard method to test new supercomputers. – Sexpartite

@user1073106 - Thanks for the info. I wasn't intending to say there were not legit reasons to calculate more digits of pi. I'm all for doing it simply to see how far we can go and as a benchmark test. I just know a large number of people that want to have the ability to get more for precision don't understand the level of precision that is practically needed can be memorized. Based on the discussion, I don't think that is the case here, but I wanted to note the fact that we're talking "fun/challenge" factor rather than practically useful (other than practical use of the challenge). – Dagoba

A very easy check is to evaluate your algorithm to 768 decimal places (don't round it). The correct digits in that neighborhood are: ...34999999837... This is known as the Feynman point. It is very easy to spot if your program doesn't output this string of nines. 768 is a fairly high precision so a potential error has plenty of time to build up when you get there. – Perni

Answer 1

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.

Input

And to answer the other question about how to know when a specific algorithm has converged to N digits: This requires that you know the convergence behavior of the algorithm. The Taylor Series of ArcTan(1) is logarithmically converging. So you'd need an exponentially large number of terms to converge - in short, don't use it. – Input

Chudnovsky's formula seems to converge linearly, both when I look at it and when I try it out naively. (It even does that when I add two consecutive terms together). Do you estimate the number of terms needed a priori and then sum the series by divide-and-conquer? Or something different? – Kylix

Yes, Chudnovsky's formula converges at a steady 14.18 digits per term. So you can divide the total number of digits by that to get how many terms you need. (Exact value is: Log(151931373056000)/Log(10) = 14.181647462725477655...) – Input

So actually what you saying is that you didn't compare 2 algorithms but found another solution. – Margoriemargot

@erikb85 Kinda. The BBP formula (to some extent) counts as a second algorithm. But by itself it isn't enough since it doesn't verify the conversion to base 10. The idea of using BBP + conversion check to eliminate the need for a second computation wasn't mine. It was first done by Fabrice Bellard in his 2009 world record. It was such a good idea that we did the same and improved upon it. – Input

@ShaquinTrifonoff what's the significance? – Ettaettari

@FunsukWangadu I can only speak for myself, but here it goes: I never actually cared about Pi itself. To me, it's just another number. The value isn't in the number itself or the 10 terabytes of useless digits, it's the methods that are used to achieve it. The centuries of math, and the decades of computer/programming research that contributed to this feat are applicable to many other fields and thus are MUCH more valuable than a hard drive of digits. To put it simply: Computing the digits of Pi is more of a sport. – Input

Wow! I see that you have now also calculated to 10 trillion digits... Any way I can get a file with all those digits without processing them for a year? :) Great answer by the way. It would be interesting to make something like the following:pi.nersc.gov, going along the lines of:i.stack.imgur.com/ogaxS.png – Scrannel

@Scrannel Up until about December last year, I had the first 5 trillion digits available for download via bittorrent. But ever since I left school, I no longer had the bandwidth to seed it. So I can only handle requests for small amounts of digits at specific offsets. There were a couple of heavy-weight mathematicians who approached me interested in running statistics on the digits. They eventually gave me a program which I ran locally. – Input

@Mystical, just stumbled on your Pi calculation site from another stackoverflow question and couldn't help but gawk and giggle at what you guys did. Loved the harddrive failures/earthquakes in the logs :) pure amazing! – Tham

Is this Piscine Patel? – Bouchier

I've read that some newer computers have built-in hardware for decimal (i.e. radix 10) arithmetic. Someone ought to use such hardware to calculate pi directly in base 10, if for no other reason than as a stress test of said hardware. – Prosthesis

Waiiiiiiit. What happens if the two results don't match? Do you have any backup algorithms or something? – Canty

@Canty If the results don't match it means either an error in the hardware, software, or implementation. It's not an error in the formula since the formulas have already been mathematically proven to be correct. So if the results don't match, it becomes an epic debugging problem. Fortunately that has yet to happen since there are lots of safeguards designed to catch errors as early as possible. – Input

What is "a lot faster than" O(N log(N)^2) ? – Transplant

Answer 2

Undoubtedly, for your purposes (which I assume is just a programming exercise), the best thing is to check your results against any of the listings of the digits of pi on the web.

And how do we know that those values are correct? Well, I could say that there are computer-science-y ways to prove that an implementation of an algorithm is correct.

More pragmatically, if different people use different algorithms, and they all agree to (pick a number) a thousand (million, whatever) decimal places, that should give you a warm fuzzy feeling that they got it right.

Historically, William Shanks published pi to 707 decimal places in 1873. Poor guy, he made a mistake starting at the 528th decimal place.

Very interestingly, in 1995 an algorithm was published that had the property that would directly calculate the nth digit (base 16) of pi without having to calculate all the previous digits!

Finally, I hope your initial algorithm wasn't pi/4 = 1 - 1/3 + 1/5 - 1/7 + ... That may be the simplest to program, but it's also one of the slowest ways to do so. Check out the pi article on Wikipedia for faster approaches.

Tris

That last formula (Leibniz formula, iirc) actually alternates addition and subtraction. – Wrigley

Answer 3

You could use multiple approaches and see if they converge to the same answer. Or grab some from the 'net. The Chudnovsky algorithm is usually used as a very fast method of calculating pi. http://www.craig-wood.com/nick/articles/pi-chudnovsky/

Overrule

Reduces the chances but I still cannot be sure with multiple approach solution, what if both are wrong. Checking on net doesn't hold validity, then why not take values off net itself. I am thinking about bbp which one is more suited ? – Lysol

@IshanSharma If the two algorithms are independent, than the chances that both computations are wrong with identical results is pretty much zero. If anything goes wrong in either computation, the final results won't match - so you know at least one of them is wrong. – Input

Answer 4

The Taylor series is one way to approximate pi. As noted it converges slowly.

The partial sums of the Taylor series can be shown to be within some multiplier of the next term away from the true value of pi.

Other means of approximating pi have similar ways to calculate the max error.

We know this because we can prove it mathematically.

Rheumatism

Seconded. I think most of the answers here are just not putting nearly enough weight on the concept of mathematical proof. Whatever your program is for calculating digits of pi, it's never going to be any more convincing than the most convincing mathematical proof that your program's method does indeed calculate pi. Which suggests a different constraint on programs that pi calculate pi: that they ought to aim as much for understandability as performance and correctness. – Quicksand

Answer 5

You could try computing sin(pi/2) (or cos(pi/2) for that matter) using the (fairly) quickly converging power series for sin and cos. (Even better: use various doubling formulas to compute nearer x=0 for faster convergence.)

BTW, better than using series for tan(x) is, with computing say cos(x) as a black box (e.g. you could use taylor series as above) is to do root finding via Newton. There certainly are better algorithms out there, but if you don't want to verify tons of digits this should suffice (and it's not that tricky to implement, and you only need a bit of calculus to understand why it works.)

Cardboard

I don't quite see how it would help spot that the 1000th digit is off by 1. You would need very precise values of sin(pi/2) wouldn't you ? – Psych

I'm not sure what to say about the previous answer, unless it is a joke or something. sin(pi/2) = 1 cos(pi/2) = 0 So, I'd say those sure converge fast. – Hircine

I guess it's not obvious to everyone that evaluating sin(x) and cos(x) to high precision is in fact much more difficult than computing Pi itself. – Input

For obvious reasons, you shouldn't use sin(pi/2) for this. Better to instead use sin(pi/6) and make sure it comes out as exactly 1/2. – Prosthesis

Answer 6

There is an algorithm for digit-wise evaluation of arctan, just to answer the question, pi = 4 arctan 1 :)

Transplant

Someone down voting this, probably didn't understand the task "digits of pi sequentially". – Transplant