There has been a discussion about PI-Indexing and irrational number theory here.

Now suppose you want to use indexes of PI to store information (file storage). To get around the fact that the indexes will be bigger than the files you're storing, you use tree of indexes - PI at a certain value is a pointer to PI at a another value.

Here the author writes:

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.

Now I'm looking at the pigeonhole principles - and I'm not connecting to why it says this is not possible. (It sounds plausible).

My question is: Why does the pigegonhole principle tell us that PI-indexing is not possible?

EDIT: A related example - here is an example of a filesystem that stores files as locations in PI.


It's explained in the first sentence of the Wikipedia entry:

The pigeonhole principle states that if $n$ items are put into $m$ containers, with $n>m$, then at least one container must contain more than one item.

So while you might be able to compress data using a clever PI-indexing algorithm, you will not be able to de-compress it to the original data, as one piece of compressed data might correspond to more than one de-compressed piece of data.

  • $\begingroup$ Thank you @Klangen. The Wikipedia entry doesn’t tell me anything about the compression method. You explanation seems to suggest that an optimisation might be used for duplicate pieces of data. I don’t see why duplicate data would hold up decompression. Your answer then suggests I might use a one-way decompression method, I’m not sure why I’d do that. $\endgroup$ – hawkeye Jun 10 at 22:18
  • $\begingroup$ @hawkeye Perhaps this post (on CS.Stackexchange) will interest you: cs.stackexchange.com/questions/44594/… It explains the same principle, but in another context $\endgroup$ – Klangen Jun 11 at 5:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.