5 ms·

You laugh now, but when we develop a trivial method to calculate pi and other irrational constants to quadrillions of digits, this will be wonderful.

baddox 12y ago
I bet I could take a few moments and come up with a proof that such a method would require P=NP.
- dtech 12y ago
  I can't find an authoritative source on this, but the algorithm used by SuperPi: https://en.wikipedia.org/wiki/Gauss%E2%80%93Legendre_algorithm https://en.wikipedia.org/wiki/Gauss%E2%80%93Legendre_algorit... seem polynomial in the number of digits you want to calculate at first glance.
  - baddox 12y ago
    Even if that's the case, wouldn't the number of digits of pi that must be computed to find a n occurrence of a random bit string of length n not be polynomial in n?
Tuna-Fish 12y ago
By the pigeonhole principle, no matter how fast you can calculate pi, you cannot actually use this to compress data. The index to relevant sequence is on average >= the size of the data to be stored.
- mrpopo 12y ago
  I was thinking so hard trying to give myself a clear explanation of why this type of compression was impossible! Thank you. Here is the pigeonhole principle on wikipedia: http://en.wikipedia.org/wiki/Pigeonhole_principle http://en.wikipedia.org/wiki/Pigeonhole_principle
- TheAuditor 12y ago
  I know :D I tried it for past 6 months and then gave up on it 2 months back, for the same reason. how ever that search gave rise to a better idea to compress files. Not yet usable but don't have all these issues with it. If you are interested you can read it at https://www.academia.edu/7620004/Advanced_Compression_Technique_For_Random_Data https://www.academia.edu/7620004/Advanced_Compression_Techni... It is based on data being represented as a position and not as the values in a computable number series .
- peterwwillis 12y ago
  I don't get how this applies. If you have a 100-gigabyte file you want to "compress" with Pi, all you have to do is find the beginning of that exact sequence in Pi and write down its location and the size (100gigabytes). As long as the binary representation of the location within Pi was less than 100 gigabytes, it is now "compressed". Why wouldn't this work?
  - mikeash 12y ago
    For most candidates, the binary representation of the location will be 100GB or more.
  - Tuna-Fish 12y ago
    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?
- haberman 12y ago
  The pigeonhole principle says that you cannot use pi to compress all data. You could certainly use this scheme to compress some data. For example, if you were storing a file containing the contents of pi (from the beginning), it would compress very well with this scheme. This is the same tradeoff that all compression schemes make. gzip can compress some files, but others will grow. The hope is that the domain of files you actually want to apply it to will shrink instead of grow. That said, given that the digits of pi are more or less uniformly distributed, there is no particular reason to believe that common bit patterns will be likely to appear sooner in pi than uncommon bit patterns. So it is unlikely that it will compress very many of the files you'd have sitting around on your hard drive. But the pigeonhole principle alone does not prove this.

baddox 12y ago

I bet I could take a few moments and come up with a proof that such a method would require P=NP.

dtech 12y ago
I can't find an authoritative source on this, but the algorithm used by SuperPi: https://en.wikipedia.org/wiki/Gauss%E2%80%93Legendre_algorithm https://en.wikipedia.org/wiki/Gauss%E2%80%93Legendre_algorit... seem polynomial in the number of digits you want to calculate at first glance.
- baddox 12y ago
  Even if that's the case, wouldn't the number of digits of pi that must be computed to find a n occurrence of a random bit string of length n not be polynomial in n?

Tuna-Fish 12y ago

By the pigeonhole principle, no matter how fast you can calculate pi, you cannot actually use this to compress data. The index to relevant sequence is on average >= the size of the data to be stored.

mrpopo 12y ago
I was thinking so hard trying to give myself a clear explanation of why this type of compression was impossible! Thank you. Here is the pigeonhole principle on wikipedia: http://en.wikipedia.org/wiki/Pigeonhole_principle http://en.wikipedia.org/wiki/Pigeonhole_principle
TheAuditor 12y ago
I know :D I tried it for past 6 months and then gave up on it 2 months back, for the same reason. how ever that search gave rise to a better idea to compress files. Not yet usable but don't have all these issues with it. If you are interested you can read it at https://www.academia.edu/7620004/Advanced_Compression_Technique_For_Random_Data https://www.academia.edu/7620004/Advanced_Compression_Techni... It is based on data being represented as a position and not as the values in a computable number series .
peterwwillis 12y ago
I don't get how this applies. If you have a 100-gigabyte file you want to "compress" with Pi, all you have to do is find the beginning of that exact sequence in Pi and write down its location and the size (100gigabytes). As long as the binary representation of the location within Pi was less than 100 gigabytes, it is now "compressed". Why wouldn't this work?
- mikeash 12y ago
  For most candidates, the binary representation of the location will be 100GB or more.
- Tuna-Fish 12y ago
  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?
haberman 12y ago
The pigeonhole principle says that you cannot use pi to compress all data. You could certainly use this scheme to compress some data. For example, if you were storing a file containing the contents of pi (from the beginning), it would compress very well with this scheme. This is the same tradeoff that all compression schemes make. gzip can compress some files, but others will grow. The hope is that the domain of files you actually want to apply it to will shrink instead of grow. That said, given that the digits of pi are more or less uniformly distributed, there is no particular reason to believe that common bit patterns will be likely to appear sooner in pi than uncommon bit patterns. So it is unlikely that it will compress very many of the files you'd have sitting around on your hard drive. But the pigeonhole principle alone does not prove this.