792

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?

Peter Mortensen
  • 30,738
  • 21
  • 105
  • 131
Ishan Sharma
  • 6,545
  • 3
  • 16
  • 21
  • 23
    more of a mathematical problem. good algorithms also give an estimate of the error. – example Jan 11 '13 at 17:17
  • 4
    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. – chris Jan 11 '13 at 17:17
  • 38
    Compare against pi? – Dave Newton Jan 11 '13 at 17:46
  • 55
    @chris: "Literally everywhere"? – Lightness Races in Orbit Jan 11 '13 at 18:28
  • 3
    @LightnessRacesinOrbit, So I exaggerated a little bit. For what I meant, [look at this](https://www.google.ca/search?hl=en&tbo=d&biw=1920&bih=947&noj=1&gbv=2&sclient=psy-ab&q=pi+digits&oq=pi+digits&gs_l=serp.3..0l10.6050.8529.0.8681.9.6.1.2.2.0.129.406.5j1.6.0.les%3B..0.0...1c.1.FlgZR2tzLBQ). 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 ;) – chris Jan 11 '13 at 18:30
  • 3
    @Mr.Mindor - There's no need to obfuscate the issue, just as there's no need to be afraid of fractions. –  Jan 11 '13 at 20:52
  • 33
    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.) – AJ Henderson Jan 11 '13 at 22:07
  • 1
    @chris "a little bit"... hmm... [25,270,000,000 results](https://www.google.com/search?q=i+-pi) vs [1,950,000 results](https://www.google.com/search?q=3.141). – Mateen Ulhaq Jan 14 '13 at 04:20
  • 3
    Use the [Spigot algorithm](http://en.wikipedia.org/wiki/Pi#Spigot_algorithms). After step `n`, the error will be less than 1/16^n. The original paper contains [a proof of why this converges to pi](http://crd-legacy.lbl.gov/~dhbailey/dhbpapers/digits.pdf). – example Jan 11 '13 at 17:22
  • 2
    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. – Barmar Jan 16 '13 at 17:46
  • 69
    Why don't you just divide by pi and check if the result is 1? (just kidding) – user541686 Jan 18 '13 at 04:26
  • @AJHenderson higher-precision PI might be used for mathematical purposes. – user176581 Jan 18 '13 at 09:14
  • 1
    @AJHenderson, finding a really big number of digits of pi is a standard method to test new supercomputers. – Martin Argerami Jan 25 '13 at 12:50
  • 3
    @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). – AJ Henderson Jan 25 '13 at 13:49
  • 3
    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. – balage Dec 27 '16 at 18:18

6 Answers6

1661

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.

Michael
  • 41,989
  • 11
  • 82
  • 128
Mysticial
  • 464,885
  • 45
  • 335
  • 332
  • 16
    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. – Mysticial Jan 11 '13 at 18:46
  • 1
    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? – tmyklebu Jan 11 '13 at 19:19
  • 23
    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...`) – Mysticial Jan 11 '13 at 19:26
  • So actually what you saying is that you didn't compare 2 algorithms but found another solution. – erikbstack Jan 13 '13 at 22:31
  • 7
    @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. – Mysticial Jan 13 '13 at 22:39
  • @ShaquinTrifonoff what's the significance? – crdx Jan 16 '13 at 10:05
  • 86
    @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. – Mysticial May 03 '13 at 21:33
  • 1
    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:http://pi.nersc.gov/, going along the lines of:http://i.stack.imgur.com/ogaxS.png – SuperPrograman Nov 23 '13 at 16:34
  • 4
    @SuperPrograman 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. – Mysticial Nov 23 '13 at 18:07
  • 8
    @Mystical, just stumbled on your Pi calculation site from another [stackoverflow question](http://stackoverflow.com/questions/11227809/why-is-processing-a-sorted-array-faster-than-an-unsorted-array) and couldn't help but gawk and giggle at what you guys did. Loved the harddrive failures/earthquakes in the logs :) pure amazing! – Joe Nov 28 '13 at 02:50
  • Is this Piscine Patel? – Null Head Mar 26 '15 at 23:46
  • 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. – Robert Lozyniak Dec 19 '16 at 20:58
  • Waiiiiiiit. What happens if the two results don't match? Do you have any backup algorithms or something? – user3576467 Aug 15 '17 at 02:00
  • 4
    @user3576467 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. – Mysticial Aug 15 '17 at 04:11
  • What is "a lot faster than" O(N log(N)^2) ? – Sam Ginrich Feb 11 '23 at 09:22
50

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.

Nosrep
  • 521
  • 7
  • 21
Larry Smith
  • 521
  • 3
  • 5
21

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/

argentage
  • 2,758
  • 1
  • 19
  • 28
  • 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 ? – Ishan Sharma Jan 11 '13 at 17:47
  • 8
    @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. – Mysticial Jan 11 '13 at 17:55
15

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.

Yakk - Adam Nevraumont
  • 262,606
  • 27
  • 330
  • 524
  • 2
    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. – Luis Casillas Jan 14 '13 at 22:21
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.)

Mazdak
  • 105,000
  • 18
  • 159
  • 188
user1974703
  • 67
  • 1
  • 7
    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 ? – Matthieu M. Jan 13 '13 at 19:12
  • 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. – BentFranklin Jan 20 '13 at 05:42
  • 17
    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. – Mysticial Jan 20 '13 at 06:04
  • 2
    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. – Robert Lozyniak Dec 19 '16 at 20:55
1

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

Sam Ginrich
  • 661
  • 6
  • 7