3 ms·

Let's say you want to store a 100kB file. There are 2^(8 x 102400) possible different 100kB files. The lowest amount of data you need to be able to distinguish

Let's say you want to store a 100kB file. There are 2^(8 x 102400) possible different 100kB files. The lowest amount of data you need to be able to distinguish the one you want from all the possible candidates is 100kB. If you could compress any file with the same algorithm, it would mean that you would necessarily have to be able to decompress the exactly same compressed file into multiple different files. Compression can only work when for every byte you take out of a file you want you need to concede to add another byte to the representation of a file you don't care about. > write down its location and the size The location of any arbitrary sequence in pi is on average a much larger number than the sequence itself.

peterwwillis 12y ago
I don't get this at all. You're talking about multiple files, which has nothing at all to do with my proposal. And I have no idea what your second paragraph means at all. The idea that a single reference point in a set is larger than the entire set itself is also ridiculous. If I have a 100-gigabyte file, and I want to point to the position in the middle, that is position 53687091200. That is an 11 byte string pointing to a single point in a 107 billion byte long file. You just do the same thing with Pi, except in this case Pi is the 107-billion byte file, and position 53687091200 points to the file's beginning point. The only thing you store is 11 bytes + the size of the file. (Of course wouldn't store the location in ASCII as binary would be a much smaller representation, but for these purposes i'm just using ASCII) Obviously the size of Pi is infinite and the size of the position would be much larger than 50-billion in, but the idea is the same. Please tell me in simpler terms how this idea does not work?
- deleted 12y ago
  [deleted]
- jdmichal 12y ago
  Let's say you wanted to encode a single decimal digit using this PI method. So, to start, you list out PI until you get all the possible decimal digits: 03 14159 26535 897 01 23456 78901 234 There, that's all of them. I cheated a bit and put a zero in the front, as the first zero in the expansion is another 10 digits or so away. So now, we can represent any decimal digit by indexing into PI! 0 - 0 1 - 2 2 - 7 3 - 1 4 - 3 5 - 5 6 - 8 7 - 14 8 - 12 9 - 6 So, what did we accomplish? Well, zero stays the same. We successfully renamed 1-6 and 9 to be new numbers. And now 7 and 8 take two decimal digits. Now, extrapolate this out to every possible 100GB file, and the binary representation of PI.
- Tuna-Fish 12y ago
  > and the size of the position would be much larger than 50-billion in, but the idea is the same. The crucial part is that the size of the position will be larger than the file you are seeking. This is unintuitive, but necessarily true for most possible files because of the pigeonhole principle. If you don't believe me, just try it out. Decide on random 4-digit sequences in pi and find their indexes. The mean of their indexes will be >4 digits. Same is true of any sequences of any length. > I don't get this at all. You're talking about multiple files, which has nothing at all to do with my proposal. No, I'm talking about multiple possible files, of which you must be able to compress and decompress any single one for your proposal to work in general. General compression is mathematically proven to be impossible. If you have a compression algorithm f() which can take any input, in order for it to be able to compress some input of length x into a form that is shorter than x, it must also compress some other input of length x into a form that is longer than x. Or, to put in another way, the sum of len(f(y)) for all possible y where len(y) = x is always greater than or equal to sum of len(y).

peterwwillis 12y ago

I don't get this at all. You're talking about multiple files, which has nothing at all to do with my proposal. And I have no idea what your second paragraph means at all. The idea that a single reference point in a set is larger than the entire set itself is also ridiculous. If I have a 100-gigabyte file, and I want to point to the position in the middle, that is position 53687091200. That is an 11 byte string pointing to a single point in a 107 billion byte long file. You just do the same thing with Pi, except in this case Pi is the 107-billion byte file, and position 53687091200 points to the file's beginning point. The only thing you store is 11 bytes + the size of the file. (Of course wouldn't store the location in ASCII as binary would be a much smaller representation, but for these purposes i'm just using ASCII) Obviously the size of Pi is infinite and the size of the position would be much larger than 50-billion in, but the idea is the same. Please tell me in simpler terms how this idea does not work?

deleted 12y ago
[deleted]
jdmichal 12y ago
Let's say you wanted to encode a single decimal digit using this PI method. So, to start, you list out PI until you get all the possible decimal digits: 03 14159 26535 897 01 23456 78901 234 There, that's all of them. I cheated a bit and put a zero in the front, as the first zero in the expansion is another 10 digits or so away. So now, we can represent any decimal digit by indexing into PI! 0 - 0 1 - 2 2 - 7 3 - 1 4 - 3 5 - 5 6 - 8 7 - 14 8 - 12 9 - 6 So, what did we accomplish? Well, zero stays the same. We successfully renamed 1-6 and 9 to be new numbers. And now 7 and 8 take two decimal digits. Now, extrapolate this out to every possible 100GB file, and the binary representation of PI.
Tuna-Fish 12y ago
> and the size of the position would be much larger than 50-billion in, but the idea is the same. The crucial part is that the size of the position will be larger than the file you are seeking. This is unintuitive, but necessarily true for most possible files because of the pigeonhole principle. If you don't believe me, just try it out. Decide on random 4-digit sequences in pi and find their indexes. The mean of their indexes will be >4 digits. Same is true of any sequences of any length. > I don't get this at all. You're talking about multiple files, which has nothing at all to do with my proposal. No, I'm talking about multiple possible files, of which you must be able to compress and decompress any single one for your proposal to work in general. General compression is mathematically proven to be impossible. If you have a compression algorithm f() which can take any input, in order for it to be able to compress some input of length x into a form that is shorter than x, it must also compress some other input of length x into a form that is longer than x. Or, to put in another way, the sum of len(f(y)) for all possible y where len(y) = x is always greater than or equal to sum of len(y).