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

Comments

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: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. Very informative.

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)

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

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 sites I've seen that has a java applet to simulate this.

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.

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