Now, we all know that it can take a while to find a long sequence of digits in π,
so for practical reasons, we should break the files up into smaller chunks that
can be more readily found.
In this implementation, to maximise performance, we consider each individual byte
of the file separately, and look it up in π.
Or - what a genius idea! - we could use Pi itself as a lookup table and use the sequence of n bytes at that position of pi as an implicit lookup table.
To store a number in range of 0 to 4,294,967,296 - you will need exactly 4 bytes.
Here is the pigeonhole principle on wikipedia:
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.
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?
It would work, exactly like you say. However, you seem to intuitively be vastly underestimating how far into pi you have to go to find a particular bit pattern.
To sharpen your intuition of this, I recommend this website: http://pi.nersc.gov/
I tried searching pi for the string "zzzz" (this is 20 bits of information according to their somewhat weird encoding scheme). The decimal position in pi for this 20-bit string was 3725869808, which takes 32 bits to represent.
The same will be true in most cases -- the offset into pi will take more space to represent than the data itself! However, in some cases data absolutely can be compressed with this pi scheme. Just not often enough to be actually useful.
However, the fact that the data will usually be larger is not what the pigeonhole principle is about.
All the pigeonhole principle says is: it's not possible for every 100 GB file to have a offset in pi that takes less than 100GB to represent. The pigeonhole principle still allows some files to be compressable with pi, just not all.
To prove this is simple: take every possible 100GB file (there are 2100G of them). Now let's suppose that for every single one you can actually find a location in pi whose binary representation is less than 100GB to represent. If you can do this, then it means that at least 2 of the input files mapped to the same location in pi (because there were 2100G distinct input files but less than 2100G pi offsets that we are allowed to use). Therefore, once "compressed", you can't tell the difference between the two input files that both mapped to the same location in pi!
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.
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?
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).
03 14159 26535 897
01 23456 78901 234
0 - 0
1 - 2
2 - 7
3 - 1
4 - 3
5 - 5
6 - 8
7 - 14
8 - 12
9 - 6
Now, extrapolate this out to every possible 100GB file, and the binary representation of PI.