81–90 of 102 posts
[1] http://en.wikipedia.org/wiki/Frederik_Pohl
[2] http://www.encyclopediaofmath.org/index.php/Gödelization
[3] http://kasmana.people.cofc.edu/MATHFICT/mfview.php?callnumbe...
Earlier quoted context omitted.
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.
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.
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?
Earlier quoted context omitted.
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.
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?
Earlier quoted context omitted.
There are 4,294,967,296 possibilities in 4 bytes. To store a number in range of 0 to 4,294,967,296 - you will need exactly 4 bytes.
Not all 32bit sequences can be found in the first 4,294,967,296 binary digits of pi. Hence you will either need more then 4 bytes to encode 4 bytes in a pi position or a lookup table to fit the 4,294,967,296 numbers, some of which will be substantially larger than 4,294,967,296, into 4,294,967,296 slots.
> They said 100% compression was impossible? You're looking at it! If the offset within pi is so large that any representation of it is larger than my data?
Yep. Consider the minimum case: assume we've described a process for finding any bitstream we want in pi while necessarily saving at least one bit. Attempt to do so for the bitstreams 00, 01, 10, and 11. If we compress 2 bits to 1 bit, by the pigeonhole principle, at least one of 0 and 1 has to represent at least 2 distinct bitstreams, which means we have lost data. A similar argument works for all compression algori…
Pedantically speaking, any data passing through a cryptographic hash algorithm is being compressed.
Earlier quoted context omitted.
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.
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.
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.
Earlier quoted context omitted.
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.
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?
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.
I'm not sure pi is proven to contain all sequence of digits. Anyone care to link a proof. The joke be on them and they might not really understand pi at all.
It isn't proven to be "normal" ( http://en.wikipedia.org/wiki/Normal_number ). There is no guarantee that any particular sequence is in pi until you've searched and found it. It's a very common fallacy that because the expansion is infinite and non-repeating it should contain every possible sequence, very simple counter examples exist. Pi can be infinite and non-repeating (as it's irrational) and only sparsely contai…