How to determine if a record breaking calculation of pi is accurate

January 13, 2013 2:37 PM

Q: "I was trying various methods to implement a program that gives the digits of pi sequentially. 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?"

A: "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. But when you get into world-record territory, there's nothing to compare against. ... "

posted by SpacemanStix (75 comments total)

Q link should go here, I think.
posted by Horace Rumpole at 2:43 PM on January 13

First link seems broken, probably should be this link instead.
posted by xiw at 2:43 PM on January 13 [1 favorite]

A programmer had a problem. He thought to himself, "I know, I'll solve it with threads!". has Now problems. two he

-- Davidlohr Bueso

posted by Malor at 2:46 PM on January 13 [79 favorites]

Q link should go here, I think.

Yes, correct. Thanks.
posted by SpacemanStix at 2:49 PM on January 13 [2 favorites]

Hey I solved a problem with two threads this

[MEMORY ALLOCATION ERROR]

week.
posted by blue_beetle at 2:50 PM on January 13 [1 favorite]

[Fixed link, carry on. ]
posted by restless_nomad at 2:50 PM on January 13

It's always fun when some world expert in something drops the science. The Stack Exchange sites are particularly good at drawing that out.

His practical advice up front ("compare your calculation to the published result") reminds me of my favorite primality testing algorithm. Want to know if some big number is prime, maybe to use as a hash table modulus or something? Just search for it in Google. Works pretty much every time, and is effectively constant time.
posted by Nelson at 2:57 PM on January 13 [1 favorite]

What a cool question (and answer); I hadn't considered this before.
posted by LobsterMitten at 2:59 PM on January 13

11:15, restate my assumptions: 1. Mathematics is the language of nature. 2. Everything around us can be represented and understood through numbers. 3. If you graph these numbers, patterns emerge. Therefore: There are patterns everywhere in nature.
posted by radwolf76 at 3:02 PM on January 13 [12 favorites]

The problem here is to rigorously define the word "pattern".
posted by Chocolate Pickle at 3:05 PM on January 13

To determine the volume of a pizza with radius Z and depth A just compute PI*Z*Z*A.
posted by w0mbat at 3:26 PM on January 13 [45 favorites]

From one of the pages:

When hard drive prices drop to pre-flood levels I'll be able to upgrade the server and host all 10 trillion decimal digits and all 8.3 trillion hexadecimal digits.

That's a beautiful sentence of science fiction there, even though it describes the real world.

The antideluvian magnetic platter trade. Wonderous.
posted by feckless at 3:38 PM on January 13 [9 favorites]

I'm curious how the world record is established. Is it just ... run a program for some number of weeks, until you have a bigger number?
posted by kafziel at 3:41 PM on January 13

I'm curious how the world record is established. Is it just ... run a program for some number of weeks, until you have a bigger number?

You also have to point at the now-ex record holder and do a Nelson "Haha!"
posted by anonymisc at 3:54 PM on January 13 [2 favorites]

kafziel, the thing is record is now multiple trillions of digits. And the people who have the record are running their programs too, and probably have much faster hardware than you have. You're chasing a moving target, and it's moving away from you very rapidly.
posted by JHarris at 4:03 PM on January 13

Can't you just subsample digits and look at their distribution? If you don't get a random mix of digits, something's up. That's not a proof that the digits are correct, but a bias in the distribution of digits would be evidence that something is wrong.
posted by Blazecock Pileon at 4:05 PM on January 13

Can't you just subsample digits and look at their distribution?

Yes, that's something you would normally try.
posted by benito.strauss at 4:11 PM on January 13 [10 favorites]

Blazecock: There are a lot of sets of digits that are randomly distributed! No discernible bias doesn't mean it's correct; it could also just be gibberish...
posted by kaibutsu at 4:17 PM on January 13 [2 favorites]

And if our tran­scend­ental lift shall find a final floor,
Then Man will know the death of God where won­der was before...
posted by BiggerJ at 4:18 PM on January 13

Yes, that's something you would normally try.

Oh, you.
posted by lambdaphage at 4:20 PM on January 13 [3 favorites]

Randomness is a very hard thing to test for. It's hard to even define well.
posted by Malor at 4:20 PM on January 13 [1 favorite]

(And, of course, there are an infinite number of random digit sequences that are not pi.)
posted by Malor at 4:21 PM on January 13

I found the last digit of pi, it's not what you would expect.
posted by borkencode at 4:44 PM on January 13 [7 favorites]

Pardon my ignorance but why?

What value is there in calculating pi out to a quadrillion places? Does it affect the price of beer?
posted by coachfortner at 4:47 PM on January 13 [2 favorites]

The issue isn't whether the digits of pi are random, but whether they are normal. The normality of pi is still an open question, so subsampling only tells you whether what you generated is normal - and if pi turns out not to be normal in the range you are generating, you would get a false negative.
posted by idiopath at 4:51 PM on January 13 [3 favorites]

coachfortner: "Pardon my ignorance but why?"

The probability that any given mathematical discovery affects the real world is low.

On the other hand, a discovery that cannot be described by existing mathematics will likely stagnate or go unrecognized. The more we can accurately describe of the mathematical world, the more likely some piece of the mathematical world is applicable to our next scientific breakthrough. And the more likely that breakthrough will happen.
posted by idiopath at 4:57 PM on January 13 [2 favorites]

So, in essence, "because it's there"?

That's fine with me. I just didn't know if there was some other application.
posted by coachfortner at 5:01 PM on January 13

That's fine with me. I just didn't know if there was some other application.

Well... naively, more digits will improve the accuracy of your computation, assuming you want an answer not in terms of pi. Whether there is any foreseeable computation where one would need trillions of digits is a separate question.
posted by hoyland at 5:19 PM on January 13

Because knowing that pi might contain every possible finite sequence of digits could be very very useful.
posted by blue_beetle at 5:25 PM on January 13 [3 favorites]

more digits will improve the accuracy of your computation

I am neither a cosmologist nor a mathematician, but I imagine that our current enumeration of pi provides enough accuracy to calculate the circumference of a sphere the size of the universe with an error margin many orders of magnitude less than one planck length. For every digit you add to pi, your calculations become an order of magnitude more accurate. That adds up very quickly.

If anybody with actual knowledge of the subject would like to confirm or deny my suspicion, that'd be swell.
posted by Scientist at 5:29 PM on January 13 [1 favorite]

What value is there in calculating pi out to a quadrillion places?

Actually, calculating pi is often used as a way to stress test software and hardware. The section on "Error-Detection and Correction" on this page. is pretty interesting.

Even on stable and non-overclocked hardware, there is a non-negligible chance of a hardware error if it is put under stress for an extended period of time. ....

Both Shigeru Kondo and myself have both experienced hardware related computational errors even on non-overclocked hardware. Between the two of us we get about one error for every 4 weeks of 100% CPU utilization...

At just a mere 8 days into the computation, a hardware error occured. Fortunately, the error-detection was able to catch the error. The error was unrecoverable so the computation was terminated and restarted from the previous checkpoint. The total time lost was about 1 day.

Consider that these folk are using hardware that may one day be used to track the flow of money, it's worth finding out how often they fail.
posted by benito.strauss at 5:30 PM on January 13 [1 favorite]

borkencode: "I found the last digit of pi, it's not what you would expect."

It's not the pinkie?
posted by radwolf76 at 5:34 PM on January 13 [1 favorite]

If anybody with actual knowledge of the subject would like to confirm or deny my suspicion, that'd be swell.

No, I don't think (though I'm someone who would compute in terms of pi) anyone actually wants trillions of digits. But strictly speaking, you are gaining precision.
posted by hoyland at 5:41 PM on January 13

borkencode: "I found the last digit of pi, it's not what you would expect."

radwolf76: It's not the pinkie?

Little jack horner sat in the corner
eating his christmas Pi.
He put in his thumb
and pulled out a plum
and said "What a good boy am I!"
posted by Nanukthedog at 6:06 PM on January 13 [3 favorites]

But strictly speaking, you are gaining precision.

Well, not exactly. This may have changed, but last I checked the greatest number of significant figures ever obtained in a measurement was about 15 (for the rubidium hyperfine frequency). Meaning that if you compute some quantity that depends linearly upon pi and the RHF the uncertainty in the measurement of the RHF will make all but the first 15 digits of pi useless.

Also, unless you're working in an atypical numerical computing environment, machine epsilon is a bigger worry than uncertainty in the value of pi will ever be. Consider the futility of storing pi to ten decimal places in, say, a C float.
posted by lambdaphage at 6:08 PM on January 13

...why?...

One reason we mathematicians work on problems like this is that in order to improve on a previous result we often need to develop a new technique. That technique is shared with the community who can then apply it to all sorts of other problems.

Also, because it's there.
posted by monkeymadness at 6:23 PM on January 13 [2 favorites]

blue_beetle: "Because knowing that pi might contain every possible finite sequence of digits could be very very useful."

Look, I was SOOOOO drunk on that Arctic cruise. I didn't think anyone had a camera that would work at those temperatures.
posted by Samizdata at 6:55 PM on January 13

Pi is only a single digit: 1 (only valid for the base Pi number system).
posted by 445supermag at 7:11 PM on January 13 [1 favorite]

...the last number's a seven. After that it's a turtle.
posted by mule98J at 7:21 PM on January 13

What value is there in calculating pi out to a quadrillion places? Does it affect the price of beer?

What value is there in drinking beer?
posted by grog at 7:39 PM on January 13 [4 favorites]

More to the point, the important results are not about pi itself, but rather about the tools and techniques used to perform this difficult (and yes arbitrary, but also extremely well defined) computation.
posted by grog at 7:46 PM on January 13 [3 favorites]

Can't you start at the highest number calculated and go forward from there? You don't have to start at 3.14 every time, right?
posted by roboton666 at 8:03 PM on January 13

coachfortner: Pardon my ignorance but why?

Scientist: I am neither a cosmologist nor a mathematician, but I imagine that our current enumeration of pi provides enough accuracy to calculate the circumference of a sphere the size of the universe with an error margin many orders of magnitude less than one planck length.

For those wondering about scale:

Using 11 digits of Π is sufficient to calculate the circumference of the earth with millimeter precision.

Using 39 digits of Π is sufficient to compute the circumference of any circle that fits in the observable universe to a precision comparable to the size of a hydrogen atom.

So, 50 digits is certainly sufficient for any practical application.
posted by ceribus peribus at 8:32 PM on January 13 [3 favorites]

All I need to know about pi is in the bible:-)
posted by nostrada at 8:36 PM on January 13 [1 favorite]

Pardon my ignorance but why?

What value is there in calculating pi out to a quadrillion places?

The most immediate practical application is likely to be cryptography. Although given current limitations, that would be an application of use primarily to organizations the size of nation-states.
posted by dhartung at 9:04 PM on January 13

Can't you start at the highest number calculated and go forward from there? You don't have to start at 3.14 every time, right?

Even better, you can calculate arbitrary digits of Π independently.
posted by ceribus peribus at 9:20 PM on January 13 [1 favorite]

Scientist:
I am neither a cosmologist nor a mathematician, but I imagine that our current enumeration of pi provides enough accuracy to calculate the circumference of a sphere the size of the universe with an error margin many orders of magnitude less than one planck length. For every digit you add to pi, your calculations become an order of magnitude more accurate. That adds up very quickly.

Pi is useful for quite a lot more than just calculating circle circumferences.

ceribus peribus: So, 50 digits is certainly sufficient for any practical application.

... of calculating a circle's circumference. Not for any possible practical application.
posted by IAmBroom at 9:36 PM on January 13 [2 favorites]

Granted, but it covers most of the applications where the accuracy of Pi is a concern. If you want to calculate and share a long irrational number for some reason there's nothing forcing you to choose Pi specifically.
posted by ceribus peribus at 9:45 PM on January 13

One day the aliens are going to turn up and be like "There's just one thing we want to know. Why did you spend all that time calculating and broadcasting τ/2? You didn't think... oh my God, you totally did, didn't you? You did!"

(whirling newspaper: MONKEYS FIXATE ON HALF τ, INCONVENIENCE SELVES FOR MILLENNIA)

And then for ever after, whenever our delegate is speaking at an interstellar conference, there'll always be this moment where another delegate is all "*cough cough* pi *cough*" and the room dissolves into giggles.
posted by No-sword at 9:54 PM on January 13 [12 favorites]

What value is there in drinking beer?
posted by grog

Brought to you by the grog lobby.
posted by Nomyte at 11:24 PM on January 13

I'm kinda into Mathematics generally (I have a Maths Degree) but I've always found these Pi decimal calculations to be really quite pointless.

Its really NOT and interesting area of Mathematics. Any self respecting mathematician should be happy just to know that "a solution exists" and not waste their time bothering with these shenanigans.
posted by mary8nne at 12:10 AM on January 14

This was some kind of awesome bizarro world math geek reverse Reddit AMA, huh?

Also, probably a silly question.... But how do we know that pi has an infinite number of digits? If there isn't a repeated sequence, how can we be certain that one day, we'll get to the seven quadrillionth digit and there won't be a remainder anymore?

Math folks, help me out here!
posted by graphnerd at 4:51 AM on January 14

Its really NOT and interesting area of Mathematics. Any self respecting mathematician should be happy just to know that "a solution exists" and not waste their time bothering with these shenanigans.

I've heard that joke before. The Mathematician examines that the water can flow from the tap, that the ice bucket can hold a sufficient volume of water to extinguish the fire, and then, satisfied that the problem has a known solution, he goes back to bed only to die in his sleep.

But seriously, there are a ton of "solutions" out there that may be guaranteed to exist by some theorem, but getting them is extraordinarily difficult and the subject of quite a lot of very interesting mathematics.
posted by RonButNotStupid at 5:12 AM on January 14 [3 favorites]

Pardon my ignorance but why?

What value is there in calculating pi out to a quadrillion places? Does it affect the price of beer?

"It concerns pi, the ratio of the circumference of a circle to its diameter. You know it well, of course, and you also know you can never come to the end of pi. There's no creature in the universe, no matter how smart, who could calculate pi to the last digit--because there is no last digit, only an infinite number of digits. Your mathematicians have made an effort to calculate it out to ... Let's say the ten-billionth place. You won't be surprised to hear that other mathematicians have gone further. Well, eventually--let's say it's in the ten-to-the-twentieth-power place--something happens. The randomly varying digits disappear, and for an unbelievably long time there's nothing but ones and zeros."
Idly, he was tracing a circle out on the sand with his toe. She paused a heartbeat before replying.
"And the zeros and ones finally stop? You get back to a random sequence of digits?" Seeing a faint sign of encouragement from him, she raced on. "And the number of zeros and ones? Is it a product of prime numbers?"
"Yes, eleven of them."
"You're telling me there's a message in eleven dimensions hidden deep inside the number pi? Someone in the universe communicates by ... mathematics? But ... help me, I'm really having trouble understanding you. Mathematics isn't arbitrary. I mean pi has to have the same value everywhere. How can you hide a message inside pi? It's built into the fabric of the universe."
"Exactly." She stared at him.
"It's even better than that," he continued. "Let's assume that only in base-ten arithmetic does the sequence of zeros and ones show up, although you'd recognize that something funny's going on in any other arithmetic. Let's also assume that the beings who first made this discovery had ten fingers. You see how it looks? It's as if pi has been waiting for billions of years for ten-fingered mathematicians with fast computers to come along. You see, the Message was kind of addressed to us."
"But this is just a metaphor, right? It's not really pi and the ten to the twentieth place? You don't actually nave ten fingers."
"Not really." He smiled at her again.

--Carl Sagan, Contact
posted by Mayor West at 5:14 AM on January 14 [3 favorites]

Even on stable and non-overclocked hardware, there is a non-negligible chance of a hardware error if it is put under stress for an extended period of time. ....

Both Shigeru Kondo and myself have both experienced hardware related computational errors even on non-overclocked hardware. Between the two of us we get about one error for every 4 weeks of 100% CPU utilization...

At just a mere 8 days into the computation, a hardware error occured. Fortunately, the error-detection was able to catch the error. The error was unrecoverable so the computation was terminated and restarted from the previous checkpoint. The total time lost was about 1 day.

Apparently, cosmic radiation can cause this.
posted by Adamsmasher at 6:52 AM on January 14 [1 favorite]

Pardon my ignorance but why?

To force the Jack The Ripper Entity from your ship's computer.
posted by tommasz at 7:20 AM on January 14 [1 favorite]

But how do we know that pi has an infinite number of digits?

Maths! It was proven a couple of hundred years ago that π is irrational. (It's also transcendental.) The proofs require a fair amount of mathematics to understand, the Wikipedia article has a decent overview.
posted by Nelson at 8:17 AM on January 14 [1 favorite]

Also, probably a silly question.... But how do we know that pi has an infinite number of digits?

It's not at all a silly question. The Wikipedia article Proof that π is irrational gives some history and a few proofs. (On preview, what Nelson said.)

By the way, this highly ranked google hit purports to give an elementary (and very short) proof that π is irrational, but beware — I'm pretty sure it's wrong. (In the last sentence, qq' is asserted to be a fixed integer, but actually q' depends on n, so it's not at all clear that qq'R_n→0.)
posted by stebulus at 8:25 AM on January 14

From the comments:

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.

Listen, Fabrice (prev iously), you've long exhausted your allotted number of accomplishments and generally cool shit. Cut it out and leave something for the rest of us!
posted by Jpfed at 8:26 AM on January 14

borkencode: "I found the last digit of pi, it's not what you would expect."

Is it too large to include in the margin of Metafilter?
posted by chavenet at 9:30 AM on January 14 [2 favorites]

Also, I would like to be alerted when the following sequences are found:

53177187714
4517734

& of course

5318008
posted by chavenet at 10:01 AM on January 14

Also, I would like to be alerted when the following sequences are found...

Too late for at least two out of three:

The string 4517734 occurs at position 13,362,553 counting from the first digit after the decimal point: 3670128923779138652545177348692589888896622787
-----
The string 5318008 occurs at position 13,809,596 counting from the first digit after the decimal point: 92282958225731901491531800884521249604684157208
-----
The string 53177187714 did not occur in the first 200000000 digits of pi after position 0.
(Sorry! Don't give up, Pi contains lots of other cool strings.)

(via)
posted by nobody at 10:10 AM on January 14

borkencode: "I found the last digit of pi, it's not what you would expect."

Is it too large to include in the margin of Metafilter?

Let P_n(X) equal the probability that an event X occurs before the nth Metafilter comment in a math post. It is obvious that

lim_{n -> infty} P_n(Fermat margin joke) = 1
posted by Philosopher Dirtbike at 12:11 PM on January 14 [2 favorites]

I imagine that our current enumeration of pi provides enough accuracy to calculate the circumference of a sphere the size of the universe with an error margin many orders of magnitude less than one planck length.

[...]

Using 39 digits of Π is sufficient to compute the circumference of any circle that fits in the observable universe to a precision comparable to the size of a hydrogen atom.

Not to pick on Scientist--because I was equally surprised by when I sat down and figured this out back when my kids were memorizing digits of pi--but it's pretty funny how hard it is to wrap your head around orders of magnitude and the size of the universe.

"Do you think maybe 10 trillion digits might be enough to compute the circumference of the entire known Universe?"

"Actually, you only need 39."
posted by straight at 3:52 PM on January 14 [1 favorite]

Has no one else noticed the hilarious last comment by user1974703?

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

I can tell you there is a wonderfully simple inductive proof for obtaining the nth digit of cos(pi/2).
posted by BentFranklin at 5:34 PM on January 14 [2 favorites]

But how do we know that pi has an infinite number of digits?

Belatedly, I saw this question, and waded through the Wikipedia article. I'm not a math whiz at all, and most of those equations are things I can't read, but this is my understanding of the problem.

A 'rational' number is any number that can be represented as one integer divided by another integer. They can be any size, gigantic or tiny, doesn't matter. (except 0 for the divisor, since that's not defined.) These numbers can be endless, either repeating or not, but they are rational if they're the result of dividing one integer by another. An irrational number is any number that cannot be represented as a ratio of integers. I believe all irrational numbers are never-ending, but not all never-ending numbers are irrational.

If I understand my skimming correctly, what they've apparently done is shown that it is impossible for both the numerator and denominator of pi to be integers, in several different ways. The first proof seems to show that because pi can be calculated as an endlessly converging series, that means that no single integer can ever stand in for that series. But even that simple proof is beyond my ability to grasp, at least quickly. And the article lists two or three more ways to prove that pi can't be one integer divided by another, all of which make about as much sense to me as explaining sorting algorithms to a caveman.
posted by Malor at 7:08 AM on January 15

(maybe less, actually, because I suspect cavemen could understand, say, a bubble sort.)
posted by Malor at 7:09 AM on January 15

These numbers can be endless, either repeating or not

Just to clarify, any endless (non-terminating) rational number must be repeating.
posted by Jpfed at 7:57 AM on January 15

I believe all irrational numbers are never-ending

Yes. Any terminating number (with, say X digits before the decimal point and Y digits after the decimal point) is a rational number (take the digits of your original number, ignoring the decimal point, and divide by a 1 with Y zeroes after it).
posted by Jpfed at 7:59 AM on January 15

all of which make about as much sense to me as explaining sorting algorithms to a caveman.

I'd suggest starting with the Proof that e is irrational; it's much simpler.

The first proof seems to show that because pi can be calculated as an endlessly converging series, that means that no single integer can ever stand in for that series.

The wording of this summary suggests that an infinite series cannot have a rational value, but this is not so. Maybe the simplest counterexample is the one that arises in Zeno's paradox:

1 + 1/2 + 1/4 + 1/8 + 1/16 + … = 2

The proof for π relies on special properties of the series in question. And there's no way to understand the first proof in the Wikipedia article, since it is not explained there, merely described, as if from a distance.
posted by stebulus at 1:01 PM on January 15 [2 favorites]

Samizdata: "blue_beetle: "Because knowing that pi might contain every possible finite sequence of digits could be very very useful."

Look, I was SOOOOO drunk on that Arctic cruise. I didn't think anyone had a camera that would work at those temperatures."

Oh, COME THE HELL ON! THAT WAS BOTH FUNNY AND PROOF I RTFA'D.

Sheesh. Tough crowd...
posted by Samizdata at 1:49 PM on January 15

And there's no way to understand the first proof in the Wikipedia article, since it is not explained there, merely described, as if from a distance.

That proof is given in detail in the last chapter of these lecture notes by David Angell. It's based on the (much loved) theory of continued fractions.
posted by stebulus at 8:19 AM on January 16

Conversation with John Conway about computing digits of pi in fractran.
posted by wobh at 9:08 AM on January 16 [2 favorites]

Some cautionary advice from alt.math.recreational: Converting Pi to binary (DON'T DO IT!)
posted by wobh at 1:41 PM on January 16 [1 favorite]

Some cautionary advice from alt.math.recreational: Converting Pi to binary (DON'T DO IT!)

Mind the color of your bits.
posted by Jpfed at 2:11 PM on January 16