A Much Bigger Piece Of Pi

Punk_Rock_Johnny points to an AP story on Pi-obsessed Professor Yasumasa Kanada. A snippet from the story: "Kanada and a team of researchers set a new world record by calculating the value of pi to 1.24 trillion places, project team member Makoto Kudo said yesterday. The previous record, set by Kanada in 1999, was 206.158 billion places." Trillion! "

Re:math question about pi

[DJPenguin]

No - pi is irrational... as far as I know this would be the case for base-n where n is of course an integer.

Re:How?

[Gudlyf]

You could always just do it with Good ol' Calculus [aol.com].

Re:math question about pi

[Dunark]

Pi is worse than irrational - it's trascendental. Merely irrational numbers can be expressed as simple expressions with finite numbers of terms, but transcendentals require an infinite number of terms.

Pi info

[Omkar]

Dr. Math's Pi FAQ [mathforum.org]. Very informative.

Re:You know ... you would think ...

[mdwh2]

Pi is represented usually by a fraction or relatively simple equation, it's just the division that makes the number go on for ever. I don't understand why we must break pi down into a decimal when it can already be represented by a simple fraction.

This is a bit misleading - since Pi is irrational, representing it as a fraction (eg, 22/7) is only an approximation. Representing these divisions usually produce an infinite expansion in decimal (if that's what you mean by "it's just the division that makes the number go on for ever"), but that number is recurring, and thus easy to work out any arbitrary digit since it repeats. This article is about working out the true value of Pi, whose decimal expansion is infinite and non-recurring, and this has nothing to do with divisions.

Taking the equation two divided by three I have found the 100000 trillionth digit ... it's "3"

Yes.. working out digits of rational numbers is slightly easy than irrational ones. Irrational numbers, by definition, can't be represented as the ratio of two integers.

Re:Accuracy?

[Zapman]

How do they check the accuracy? Easy!

See:

http://www.math.hmc.edu/funfacts/ffiles/20010.5. sh tml

You can figure out what any digit of pi is, without bothering with any of the preceding digits.

This only does base16, however I remember seeing one that was for base10 as well. When in doubt, google.

Re:Well ... what is it?

[mfos.org]

Actually, since this is not text data, but numbers, you don't need to waste a whole byte to store a number, if my calculations are correct (probably aren't, hey its early) you only need 514 billion bytes

Re:Well ... what is it?

[mfos.org]

Here's the magic

You have a 1.24 trillion digit base ten number

10^1.24e12

Now we find out how many digits long it'll be in base 2, x

10^1.24e12 = 2^x
x = ln(10^1.24e12)/ln(2)

x = 1.24e12 * ln(10)/ln(2) = 4119190837660.6

Now divide by 8 to get bytes, and viola!

515e9

Re:math question about pi

[wass]

Nope. Do you write the number 2 as '1' in binary (base 2)?
sorry, but in base pi, pi would be written as 10.

(fyi, i made the same mistake back in the day also)

Comment removed

[account_deleted]

Comment removed based on user account deletion

Re:Why doesn't math deal with Reality well?

[Anonymous Coward]

In the former case, math does deal with it well; it's 10/3 ft. In the latter case, all measurements have a certain accuracy, and the measurement of the radius you get isn't nearly as exact as saying the radius is 5/pi (assuming, of course, the circumference is EXACTLY 10 ft.)

Re:How to calculate PI yourself

[jkramar]

That's very wrong; the ninth digit after the decimal point is not 4 but 3. Not only that, but the toothpick technique is not fast at all.

Another well-known but slow algorithm is as follows:
pi=4/1-4/3+4/5-4/7+4/9-4/11+4/13-4/15+4/ 17-4/19+.. .

Re:Well ... what is it?

[Ryan Amos]

He was calculating the size of a text file containing pi, and for that, he was correct. Actually, by its nature, pi should not compress very well, if at all. The numbers in pi have no pattern (I forget the proof, but there is one) so most compression algorithms wouldn't be able to do much with it.

Re:OK, now this is overkill

[Ryan Amos]

Hrm.. Well, as one of my Computer Science teachers once told me (in a discrete math class).. Mathemeticians do things because it interests them. The fact that it often has no practical application is why they are often cold, bitter and broke. :)

sequence arguement is false

[Anonymous Coward]

01 001 0001 00001 000001 ... is an infinite, non-repeating sequence of "whole numbers." Find me the subsequence with a "2" in it.

Re:One simple question

[SpaceRook]

Why?

Well, if you read the article, you would know why. Mapping out a very large number like that is useful for testing the accuracy of supercomputers. Also, the research process spins off lots of discoveries. Someone who mapped out pi to 1.24 trillion decimal places probably learned a couple neat tricks along the way.

It's called Buffon's Needle

[Flamesplash]

You could at least give credit where due ;)

Here's one of the nicer [angelfire.com] sites I've seen that has a java applet to simulate this.

Google nitpick

[Anonymous Coward]

"Google" - search engine.
"Googol" - 10^100.

Re:One simple question

[Anonymous Coward]

They don't need to do so, as one can prove [shu.edu] that Pi is irrational in advance.

Re:Signature of God?

[Teach]

Chances are that if you look long and hard enough, widening your parameters for what's acceptable enough, you will find something.

Granted. Though a lot of people go from there into assuming that certain things are much more probable than they actually are. For example, though I haven't looked through the digits of pi itself, I feel pretty confident that no 500x500 string of mostly zeros occurs. In fact, the chances of it doing so are so astronomically slim that it would be easier to believe that an intelligent designer had put it there than that it occurred by chance.

The Mathematics of Monkeys and Shakespeare [nutters.org] is one of my favorite articles to point intelligent readers to that believe that whole infinite number of monkeys typing would eventually produce Hamlet idea.

Re:How To Calculate Pi

[deppe]

You can also use GNU bc for this:

$ bc -l
bc 1.06
Copyright 1991-1994, 1997, 1998, 2000 Free Software Foundation, Inc.
This is free software with ABSOLUTELY NO WARRANTY.
For details type `warranty'.
scale=50
a(1)*4
3.14159265358979323 8462643383279502884197169399375 08

Nope.

[starsong]

Area of a circle is

(pi)*( radius^2 ), not (pi*radius)^2.

And, the volume of a sphere is

(4/3)*(pi)*( radius^3 ), again not involving pi^3.

Also, 'cause the Earth isn't a perfect sphere you'd have to do a LOT of measurement. :)

Re:Google nitpick

[sameb]

Just ask google's history [google.com] page.

PI = 3

[PrimeNumber]

Only in Indiana [uwaterloo.ca]

Information theory

[stud9920]

You, Sir, despite your low member number, would get an F- for information theory at the university I was tought and now teach.

There is nothing that compresses to one bit. There is such thing as a most efficient way of encoding any message. Counted in bits. and no, not just one bit. One bit would just contain enough information to say "Pi" or "Not Pi". "Not Pi" would according to my intuition not be an acceptable answer, you also have to say "What kind of 'Not Pi'". And that takes bits. You forgot that your algorithm is supposed to possibly generate all possible messages, or else it's "not fair".

Pi would not compress at all, given it's an infinitely long number. (To be precise, it's length would be reduced from inf to inf/(alphabet entropy) which is still inf, although a "smaller" inf). If you are content with a finite number of digits, its length would be reduced by about a little more than three bits per decimal (because log2(10)=3.???) with any decent entropy encoder. You could try to reduce this further by taking two decimal digits at once, but unfortunately it would not work, as not only are Pi's digits uniformly distributed from 0 to 9, pairs of digits are also distributed uniformly from 0-99, so you would remain with 6.???? bits (log2(100)) per decimal digits pair.

Another approach you might take, if you want infinite precision (silly on a finite machine), or more generally random precision, is to write a code in a predetermined programming language, in this case a series developement, or whatever the number thorists use nowadays to calculate pi, and decide that the "decompression algorithm" is a compiler (that is perfectly legal, as any finite message can be passed that way, eg "#include <iostream> int main(){cout << "The message";}").

My idea is that the c compression algorithm would be beat by a perl compression. Maybe try in BrainFuck, it might beat perl, but BF sucks at multiplications.

Anyway, the most optimal compression for pi is probably saying "Pi" by itself. Any decent geek knows at least one way to calculate that/ find it on project gutenberg/whatever. But don't ever think that you could compress it to two bytes or less : you gotta be sure that I will not understand "the string of decimal digits a.k.a. Pi, do write it in numbers when decompressing", not just "mu turned over", "Pi the string" or "Private investigator". This certainty takes bytes.

Another example is : "you cannot encode '3 4 8 15 3.141592653 78 54' as '3 4 8 15 pi 78 54', because that would increase the number of symbols in the alphabet, and all the other symbols would have to contain more bits as a result, so the compressed message length would suffer- hope there are a lot of 'pi' in the compresed message".

I must leave now, gotta go bowling with friends. Start your flames, I can see blatant holes in my reasonments. Hope you get the point. Mailing a link to the message to my signal theory professor (formally one of my bosses), so I will suffer if I told bullshit.

Re:Information theory

[Jerf]

A compression function is a mapping from input to output. A decompression function maps from all possible outputs of the compression function, back to all possible inputs (though there may be some illegal input to the decompression function). As long as decode(code(x)) = x for any x in the domain, it's a "compression" function, even if possibly a really bad one. There's an infinite number of such functions but most of them are terribly uninteresting. For instance, a particular 'code' might repeat x twice and one of its corresponding 'decode's might cut the input in half again; it meets the definition but we'd never be interested in that.

Different functions perform better or worse in different domains, which is why we have "zip", "gzip", "bz2", "shl" or whatever the lossless audio encoder is, and all kinds of other compressions.

It is trivial to define a function that maps one bit to pi, even if pi is defined as some infinite sequence, instead of a finite symbol representing the infinite concept. You just do it.

Where all numbers are in binary:

decompress(x) = { (the infinite binary encode of pi) if x == 1
what gunzip would do if x != 1 }

Perfectly permissible since "1" isn't a legit gunzip file.

compress(x) = { 1 if x == (the infinite binary encoding of pi)
what gzip would do if x != pi }

For your choice of binary encodings of real numbers that makes sense in this domain.

You seem to have neglected that strings have length, and that just because a given thing compresses down to one bit, does not mean that all things the compression scheme produces will be one bit. In fact, that's impossible for obvious reasons.

There's a perfectly well defined mapping that exists. Of course you can't implement this directly since x can be infinite in this case, and would thence take an infinite amount of time to check if x is pi for the compression case, but it's the same kinda thing as "you can't implement a Turing Machine because you can't have an infinite tape." The function itself, like Turing Machines, is perfectly well defined.

There's nothing unrealistic about this, either; the same principles underly the proof that no compression algorithm can compress all input. You forget that there is no "one true representation" of anything; we can define symbols to mean whatever the hell we want.

(This assumes gzip is defined for infinite input, which IIRC it is, since it's a stream-based compressor; conceptually, there's no reason that gunzip won't perfectly happily run forever on an infinite input, giving perfectly well-defined output, as long as the machine in question has infinite memory.)

Pi would not compress at all, given it's an infinitely long number.

Trivially wrong anyhow, even with your misunderstandings. The people in the article who generated over a trillion digits of pi did not pull them out of their ass; there's a mathematical procedure that produces the digits of pi, as many as you have time to compute. Realistically, that means that pi is compressed as the Turing Machine that spits these digits out, and this Turing Machine is fed to the Universal Turing Machine, which "decrypts" (normally we wouldn't use that word, but a UTM fits into the definition of a decryption function, mapping input to output) the output into the string of numbers. The Pi TM is finite, the output is not. Again, you can't run in finite time, but conceptually, the TM represents all of Pi, given enough time. (It "limits" to it, if you like, as time goes to infinity.)

(The corresponding encryption routine for UTM as a decryption routine is much, much tougher, beyond human capability to perform optimally, and often at all; many interesting things about that have been proven.)

A friend of mine has toyed with a theory of "computable" numbers, lying somewhere between the reals and the rationals. A "computable" number is one where there exists a Turing Machine that will output it, as time goes to infinity. Since there are fewer TMs then real numbers, it's clearly smaller then the set of reals, yet equally clearly, it's larger then the rationals, since it includes things like Pi, e, and, most interestingly, any number we could ever conceivably communicate to each other in such a way that we could construct it. That's the most interesting part of it; it's not the full reals, yet you can't point to a real number or reference one that is not in this "computable" set. Not directly germane, but perhaps interesting to anybody following the posts this deeply.

Anyway, the most optimal compression for pi is probably saying "Pi" by itself.

Ironically, you further demonstrate a decompression algorithm ("simplifying an expression into its decimal equivalent according to the corpus of human mathematical knowlege") that decompresses the sixteen-bit phrase "Pi" into the infinite decimal sequence.

My idea is that the c compression algorithm would be beat by a perl compression.

And what is that supposed to mean, anyhow? Algorithms exist independently of their implementation in a given language!

Your understanding of information theory is skin deep; you recall some of the results but you do not understand the deeper logic. I'm not an expert but I'm pretty confident that this post is accurate enough for Slashdot. (I'd be a bit more careful with definitions and domain specifications for a class assignment, but this isn't, and it's long enough.) The exactly compressions techniques you learned are just a special case that happens to be useful in the real world, not the be-all end-all of compression.

Re:Yes, but...

[matrix29]

while it's true (I think) that any fininte sequence of digits will eventually appear in a non-repeating, infinite sequence, I think the point in the book was that the odds of our being able to find it, given the tiny tiny tiny tiny tiny tiny portion of the number space we're able to search with our extremely finite computing power, would be evidence that it was placed there if we ever did manage to find it.

Put another way, it would have to be hanging in easy reach for us to be able to find such an insanely improbable thing as (say) a 500x500 block of pre-arranged digits. In base 11, that would be 11^(25,000), a number too hideous to contemplate, and think of the size of the space you'd need to search before such a number would be found just based on probability. So if we found such a thing, we either beat bazillion^bazillion-to-one odds, or we found something that was left there for us. Interesting.

Actually, base converting Pi in to Base 11 is actually pretty damn EASY.

Here is the number
3.1415926535897932384626433832795
3 in Base 11 = 3
Now the rest is simple.
Multiply 0.1415926535897932384626433832795 by 11
Take the number past to the left of the decimal point and use this as your first digit of Base 11 Pi. In this case it is = 1.
Subtract that number and multiply by 11 again.
The number you get is 6.

Now if you Wash - Rinse - Repeat you'll arrive at the number in Base 11 (3.16150702865A485235215...)
Pretty simple? You can do this quickly with other bases without hitting negative powers of the base number. You can also convert a number in another base quickly using the technique from my earlier post in this Slashdot chat. The trick is to convert your target base number into the base that you're converting from. It works for all decimals just like RADIX works for all integers. Do a find for "matrix29" on this page and you'll hit my previous post right off.

You can also convert to non-integer bases (ergo Base 7.886) but the method is a tad more awkward.

Think about it more...

[efuseekay]

Dude, they measure it to 1.24 Trillion, not 10^(Trillion).Someone had pointed that out, but...

If you think about it, you could not have fitted the entire observable universe with enough paper to record (even if you write in very very very very small fonts) the number of decimals if you know PI to 10^(Trillion).

In fact the entire observable universe had about 10^120 atoms. So you are out of luck very soon. (You can imagine packing more atoms, but then the universe will become too dense and collapse on herself so fast you won't have time to expand to her current volume).

Re:Think about it more...

[Anonymous Coward]

Think about it again yourself...

I was saying that there are as many zeros in 10^trillion as there are decimal points in pi.

My calculations work.

Re:Pi is equal to an even 3 apparently

[Madman27]

This is from the Old Testament. (found in my History of Pi book).

"Also, he made a molten sea of ten cubits from brim to brim, round in compass, and five cubits the height thereof; and a line of thirty cubits did compass it round about."

Egyptians and Babylonians had a much better approximation of Pi, long before the Bible was written. The Babylonians calculated Pi to be 3 1/8. The Egyptions had it at 4 * (8/9) ^ 2.

I'm not saying that the Bible was making an absolute claim that Pi was 3, as they're attempting a general description of an object in the quote. But my main point was that this senator took it literally, and I'm sure he had a large backing of complete idiots.

Re:PiHex

[cperciva]

Colin Percival is 'on' slashdot, I'm sure he can provide more details

Uh, guys, I'm not Hastur. I'm not summoned by people simply mentioning my name; you have to actually send me an email.

Right, PiHex. The various posters here have more or less gotten the details right: The BBP formula expresses Pi as an infinite sum, and the BBP algorithm tells you how many terms you need to evaluate, and how to evaluate them starting at a given bit position.

You split this up by having each processor compute the sum of a small set of terms. I did this initially over email, but since coordinating 1700 machines by hand is rather time consuming, I eventually wrote a server for it. Incidentally, PiHex was the first program I wrote in C, and the PiHex webserver (which was running on my windows 95 box behind a cable modem) was my first experience with sockets programming.

There are no similar methods known for Pi in other bases, although it is possible to compute individual "digits" of Pi^2 in base 3.

A "classical" computation of Pi, starting at 3.141... requires arithmetic on n-digit values (where n is the number of digits you want to compute); the addition is easy, the multiplication is done with FFTs, and everything else is done with Newton iterations.

Big FFTs require a single all-to-all communication stage; this means using lots of bandwidth; it also means that big FFTs are unusually difficult on "structured" interconnects (eg, meshes) because data needs to be sent everywhere instead of simply to each processors' neighbours.

Incidentally, I'm now a doctoral student at Oxford University [ox.ac.uk] and my research project is extending the whole "distributed computing" model to more interesting problems -- including large FFTs and a classical computation of Pi. I had planned to calculate a trillion digits, but I guess now I'll have to go a bit further than that.

Re:math question about pi

[Smurf]

However, can someone explain to me what 1 base pi is? 11 base Pi?

I think 1 base Pi would simply be: 1*Pi^0 = 1

And 11 base Pi: 1*Pi^1 + 1*Pi^0 = Pi + 1

And 0.1 base Pi: 1*Pi^-1 = 1/Pi

Re:Signature of God?

[superyooser]

If you feel there's only one god, then for you, that is true.

I don't know what it means to "feel" truth. That doesn't make any sense. I study and observe truth which points to further truth which must be taken on faith. It is reasoned belief.

Reality is not based on belief; it is for belief to be based on reality. I cannot will something into existence by believing in it. If I believe myself to be a physician, will you let me do surgery on you? Won't it be true if I believe in it? According to your reasoning, yes. I'd also like to believe in world peace. Voila! Now it's true! Now I'm believing that Santa Claus is real. This is cool! And grandly delusional.

It harms me none.

You and I are standing in a busy street. My point of view is that a Mack truck is ten feet away and driving toward us at 60 MPH. My belief is that if you and I and everybody else in the lane does not immediately run to an area of safety, we will all be run over by the truck and die. Somebody glued to their GameBoy will have a different point of view, but the reality of the situation will affect him as equally as it will affect me. The Mack truck will run over you even if you don't believe it's real or harmful. Other examples: Failure to believe that fire is hot will harm you. Believing that you are using Unix when in fact you are using DOS is sure to drive you nuts. Belief won't change your OS. You have to install an OS to change the reality. This is really common sense.

Reality is universal and transcendental. You have to adapt your beliefs to reality. Reality will not adapt itself to your beliefs. It couldn't even if it "wanted" to, because people believe different things. It is what it is, and you will be adversely affected if you believe it to be something it's not.