🔒 Locked

MP3-Beating Compression (for real!)

Started by kSquared May 23, 2006 at 12:22 AM 72 replies 12.8k views

Original Post

May 23, 2006 at 12:22 AM

(1) Pi is a transcendental number with no apparent pattern; its decimal representation continues on forever. (2) In turn, this means that for every finite string of numbers, the probability is 1 that this string is somewhere in pi. (3) A file is a sequence of bytes, which can be expressed as a finite string of numbers. (4) At least one O(1) algorithm exists to compute the nth digit of pi. (I use "O(1)" in the sense that the algorithm does not require that you compute digits 1 through (n-1).) Claim: All you need to compress any file are exactly two numbers: the starting index i of the digit of pi at which the file's string begins, and the length L of the string. To decompress, compute digits i through i + (L - 1), convert to bytes, and you've reconstructed the file. Discuss the truth or falsity of this claim. Also discuss whether this is currently a practical method of compressing files given a standard desktop computer. If not, could it ever be? [edit:] Note that it has yet to be shown whether pi exhibits normality or not, so the validity of (1) is up in the air. But as far as we can tell empirically (out to about a trillion digits), it certainly looks that way. [Edited by - kSquared on May 23, 2006 8:37:19 AM]

ArchWizard

May 23, 2006 at 12:24 AM

Mithrandir proposed this idea long ago.

fadilthrejk

May 23, 2006 at 12:26 AM

wouldn't that require a ridiculously large file with pi to an equally large number of digits, such that the space the compression generates is outweighed by the space pi takes?

or you could just calculate the pi on the fly, but then the compression/decompression could take years

Daerax

May 23, 2006 at 12:29 AM

Hmmm... This looks like a homework problem. :)

On a more serious note, I assume there is some fallacy you wish to be pointed out, which is already known to you?

Washu

May 23, 2006 at 12:29 AM

Quote:
Original post by kSquared
(1) Pi is a transcendental number; its decimal representation continues on forever.

Obviously wrong, everyone knows that Pi is 22/7.¹

Quote:

(2) In turn, this means that for every finite string of numbers, the probability is 1 that this string is somewhere in pi.

I smell wrongness!²

Quote:

(3) A file is a sequence of bytes, which can be expressed as a finite string of numbers.
(4) At least one O(1) algorithm exists to compute the nth digit of pi. (I use "O(1)" in the sense that the algorithm does not require that you compute digits 1 through (n-1).)

Claim: All you need to compress any file are exactly two numbers: the starting index i of the digit of pi at which the file's string begins, and the length L of the string. To decompress, compute digits i through i + L, convert to bytes, and you've reconstructed the file.

Discuss the truth or falsity of this claim. Also discuss whether this is a practical method of compressing files. If not, could it ever be?

[grin][grin][grin][grin][grin][flaming]
[grin][flaming][flaming][grin][flaming][grin]
[flaming][flaming][grin][flaming][flaming][grin]
[grin][flaming][grin][grin][flaming][grin]
[grin][flaming][grin][grin][flaming][grin]
[grin][flaming][grin][grin][flaming][grin]
[flaming][grin][grin][grin][grin][flaming]

¹ I have derived this by the power of Caek
² If you aren't sure about this, think about the transcedental number: 0.101001000100001000001...

[Edited by - Washu on May 23, 2006 12:29:04 AM]

Endar

May 23, 2006 at 12:31 AM

I have a feeling that for each significantly string of numbers, assuming that the string is an actual file to be compressed, that the time taken to actually generate pi to the start of the sequence through to the end of the sequence would generally be much larger than the time it takes to compress the sequence with another, more commonly used algorithm.

kSquared

May 23, 2006 at 12:31 AM

Quote:
Original post by Daerax
Hmmm... This looks like a homework problem. :)

Anyone who's foolish enough to post homework problems in the Lounge richly deserves the resulting quality of answers they get. [wink]

cowsarenotevil

May 23, 2006 at 12:35 AM

Quote:
Original post by kSquared
Discuss the truth or falsity of this claim. Also discuss whether this is a practical method of compressing files. If not, could it ever be?

No, it's bogus. Counting theory and such. Assuming Pi is an effectively random number, it would be random whether a file's start and end incices take up more or less space than the original file. You'd need some number with the more common strings found in a type of file placed first (so they'd have smaller start/end indices) for it to be effective.

The generation of such a number is left as an exercise to the reader :D

EDIT: Replace "end index" and variants with "length of file," because I can't think.

smart_idiot

May 23, 2006 at 12:35 AM

(1) For random data, the data required to store the position in pi along with the size might be smaller than the original data, but there's a good chance it'll be bigger.
(2) Ordered (non-random) data is just as likely to be found as pure random data, so existing compression algorithms are already better.
(3) Finding where in pi a chunk of data is would take forevers.
(4) Assuming our data started right at the beginning of pi (best case scenario), we only know enough digits of pi for about 48 GB of data.

Antisheep

May 23, 2006 at 12:42 AM

Abstract idea, but too farfetched. Good thinking though.

Daerax

May 23, 2006 at 12:58 AM

Quote:
Original post by kSquared
(1) Pi is a transcendental number with no apparent pattern; its decimal representation continues on forever.
(2) In turn, this means that for every finite string of numbers, the probability is 1 that this string is somewhere in pi.
(3) A file is a sequence of bytes, which can be expressed as a finite string of numbers.
(4) At least one O(1) algorithm exists to compute the nth digit of pi. (I use "O(1)" in the sense that the algorithm does not require that you compute digits 1 through (n-1).)

Claim: All you need to compress any file are exactly two numbers: the starting index i of the digit of pi at which the file's string begins, and the length L of the string. To decompress, compute digits i through i + (L - 1), convert to bytes, and you've reconstructed the file.

Discuss the truth or falsity of this claim. Also discuss whether this is a practical method of compressing files. If not, could it ever be?

Okay this would only work if the data happened to be equivallent to the next "(l-1)" digits of pi after digit "i". Assuming that our number k, which represents our file, digit's are sufficiently random and equidistributed then the k is already uncompressible. It will take an algorithim of at least k's bits to compute all its digits, unique to k.

"Also discuss whether this is a practical method of compressing files. If not, could it ever be?"

No, but it could be if pi k turns out to not only be not transcendental but not irrational as well heh.

[Edited by - Daerax on May 23, 2006 1:58:11 AM]

kSquared

May 23, 2006 at 1:06 AM

Quote:
Okay this would only work if the data happened to be equivallent to the next "(l-1)" digits of pi after digit "i".

It is, by definition. That is, you choose i such that those L digits represent the file. Of course, how much effort it takes to actually find that i is another matter entirely. [wink]

Quote:
It will take an algorithim of at least k's bits to compute all its digits.

If you meant, "to write down the algorithm takes at least k bits", that's definitely incorrect. I can write down the formula in about 250 characters of text; are you saying that it will be impossible to compress files larger than 250 bytes?

Boder

May 23, 2006 at 1:09 AM

How long would it take to compress and decompress?

Dmytry

May 23, 2006 at 1:16 AM

Quote:
Original post by kSquared
(1) Pi is a transcendental number with no apparent pattern; its decimal representation continues on forever.
(2) In turn, this means that for every finite string of numbers, the probability is 1 that this string is somewhere in pi.
(3) A file is a sequence of bytes, which can be expressed as a finite string of numbers.
(4) At least one O(1) algorithm exists to compute the nth digit of pi. (I use "O(1)" in the sense that the algorithm does not require that you compute digits 1 through (n-1).)

Claim: All you need to compress any file are exactly two numbers: the starting index i of the digit of pi at which the file's string begins, and the length L of the string. To decompress, compute digits i through i + (L - 1), convert to bytes, and you've reconstructed the file.

Discuss the truth or falsity of this claim. Also discuss whether this is a practical method of compressing files. If not, could it ever be?

Firstly, if pi is transcendental number that doesn't repeat itself it doesn't necessarily follow that you will find any string in pi *. This would need additional proof.
Second, even if you necessarily find your string in pi it is rather easy to show that i will need no fewer bytes to store it (on average) than original information.

* example: take digits of any random-looking transcendental number and replace every instance of "123456789" with "187654329" (if any). Resulting number is transcendental too, doesn't repeat itself [replacement won't make it repeat itself] and also continues forever. The pattern of lack of "123456789" may be invisible; yet you can't find "123456789" in it.
[The existence of algorithm to find nth binary digit of pi already implies there is some pattern btw]
edit: changed replacement so it works with sequences like 12345678123456789

[Edited by - Dmytry on May 23, 2006 2:16:18 AM]

Daerax

May 23, 2006 at 1:20 AM

Quote:
Original post by kSquared
Quote:
Okay this would only work if the data happened to be equivallent to the next "(l-1)" digits of pi after digit "i".

It is, by definition. That is, you choose i such that those L digits represent the file. Of course, how much effort it takes to actually find that i is another matter entirely. [wink]

That is cheating but makes this alot more interesting.

Quote:
Quote:
It will take an algorithim of at least k's bits to compute all its digits.

If you meant, "to write down the algorithm takes at least k bits", that's definitely incorrect. I can write down the formula in about 250 characters of text; are you saying that it will be impossible to compress files larger than 250 bytes?

This is no longer a case since I did not realize that we have already magically found a sequence in PI which represents our number. But I am going to pick at that thread a bit. But in essence I felt it was a valid assumption to hold that the random number k composed of a random sequence of digits was a normal number. I jumped to the assumption that this number would also be uncomputable. Unlike PI, which is. Give me some time. I am being rather hasty and making some oatmeal atm.

Sneftel

May 23, 2006 at 1:27 AM

You know, searching for the file in pi would work, but what about searching an easier irrational number instead? Like:

0.12345678910111213141516171819202122232425...

Seems like that'd be much more convenient.

Dmytry

May 23, 2006 at 1:32 AM

Quote:
Original post by Sneftel
You know, searching for the file in pi would work, but what about searching an easier irrational number instead? Like:

0.12345678910111213141516171819202122232425...

Seems like that'd be much more convenient.

Way Walker

May 23, 2006 at 1:40 AM

Quote:
Original post by kSquared
(1) Pi is a transcendental number with no apparent pattern; its decimal representation continues on forever.
(2) In turn, this means that for every finite string of numbers, the probability is 1 that this string is somewhere in pi.
(3) A file is a sequence of bytes, which can be expressed as a finite string of numbers.
(4) At least one O(1) algorithm exists to compute the nth digit of pi. (I use "O(1)" in the sense that the algorithm does not require that you compute digits 1 through (n-1).)

If (1) is strengthened to pi (it really needn't be pi) being a normal number, then it would "work", assuming the constant term in (4) isn't too large and common values for i take fewer bytes to represent than the file did. (Well, it'd work without these last two assumptions, it just wouldn't be practical.)

Better luck might be had by taking many slices of pi (forgive me, I'm sleepy), or even varying the number, and putting them together to make the uncompressed file.

Way Walker

May 23, 2006 at 1:42 AM

Quote:
Original post by Sneftel
You know, searching for the file in pi would work, but what about searching an easier irrational number instead? Like:

0.12345678910111213141516171819202122232425...

Seems like that'd be much more convenient.

Hmm... I seem to remember there being a relatively easy way of getting the nth digit of that sequence, but I don't know if it was very fast.

Sneftel

May 23, 2006 at 1:58 AM

Here's the equivalent in binary:

0.0100011011000001010011100101110111...

In this case, a sequence of length b with binary value n may always be found starting at sum(1,b-1,k*2^k)+n*b. Bingo! MP3 is beaten!

Topic Locked

This topic has been locked by a moderator. New replies are not allowed.