4 ms·

I know it was meant as a bit of a goof, but i always thought that the "look up the file in pi!" idea was a clever way of doing compression[1], exploiting the fa

I know it was meant as a bit of a goof, but i always thought that the "look up the file in pi!" idea was a clever way of doing compression[1], exploiting the fact that pi is normal and thus any given sequence of numbers will happen eventually, meaning that any given file that could possibly exist will show up eventually. Using this, you could theoretically just store two numbers to compress anything, a beginning point and an end point for its position in pi. I'm aware this would be unbearably slow and the numbers to store really big files might end up taking more memory than LZMA, so I don't need a lecture about it, I just thought it was an interesting idea. [1] https://github.com/philipl/pifs https://github.com/philipl/pifs

crazygringo 6y ago
It's not just slow but it wouldn't be compression either. On average, the length of the number required to point to the starting digit will be the same length as the data you're trying to compress. It would be 0% compression in the long run.
- treesprite82 6y ago
  > On average, the length of the number required to point to the digit will be the same length as the data you're trying to compress. It would be 0% compression in the long run Worse than 0%. The average position of numbers 0000-9999 in pi is 9940, for example. I believe ideally you'd want a De Bruijn sequence (https://en.wikipedia.org/wiki/De_Bruijn_sequence https://en.wikipedia.org/wiki/De_Bruijn_sequence - "optimally short with respect to the property of containing every string of length n at least once") but even that won't get 1:1 compression.
anuragbiyani 6y ago
It's a commonly held misconception that Pi is proven to be normal - it is NOT (it is a conjecture as of now) [1] [2]. Proving normality of number is a very hard problem, and hardly any numbers outside of purposefully constructed ones (such as Champernowne's constant [3]) are proven normal. In fact it's not even proven that every digit occurs infinitely many times in the decimal expansion of Pi. [4] So https://github.com/philipl/pifs https://github.com/philipl/pifs is wrong in claiming that all byte stream will exist somewhere in Pi (it's not proven). Also it's worth calling out that even if Pi was Normal it will likely take more space to store the indices of two location as it will for original data itself (for at least majority of the integers), so it's not much of a "compression" strictly speaking. It's easy to see how this will work out for a known normal number - Champernowne's constant [3] -> Unlike Pi, Champernowne's constant is guaranteed to contain all the possible natural number sequences, but storing just the starting index of them in this constant is going to take much longer than the entire number itself (e.g., number "11" start at index 12 (1-indexing), number "12" starts at index 14, and so on - the size of index increases much faster than integer being looked up itself). [1] https://mathworld.wolfram.com/NormalNumber.html https://mathworld.wolfram.com/NormalNumber.html [2] https://math.stackexchange.com/a/216578 https://math.stackexchange.com/a/216578 [3] Champernowne's constant (in base 10) is the concatenation of all positive integers and treating them as the decimal expansion (following "0."): 0.12345678910111213... It can be trivially seen that it contains all natural number strings. It is also proven to be Normal in base 10 (which is a stronger property). See https://en.wikipedia.org/wiki/Champernowne_constant https://en.wikipedia.org/wiki/Champernowne_constant for details. [4] https://en.wikipedia.org/wiki/Normal_number#Properties_and_examples https://en.wikipedia.org/wiki/Normal_number#Properties_and_e...
- tombert 6y ago
  I know it's just a conjecture, it's actually mentioned in that Github page that it's a conjecture. That said, if we assume it's true, it's an interesting thing to think about.
  - anuragbiyani 6y ago
    I was referring to the claim made in the README's section: "Every file that could possibly exist?", which is written as if it's a proven statement: > That's right! Every file you've ever created, or anyone else has created or will create! Copyright infringement? It's just a few digits of π! They were always there! But yes, after you mentioned it, I see that the conjecture disclaimer is mentioned in a section at top ("What does π have to do with my data?") and afterwards the fact is assumed as true in rest of the README.
jonny_eh 6y ago
How would that be any better than "point to a spot on the number line"?
- tombert 6y ago
  I suppose it's not functionally different, since any binary can be expressed in terms of an integer. My tail has been thoroughly planted between my legs.

crazygringo 6y ago

It's not just slow but it wouldn't be compression either. On average, the length of the number required to point to the starting digit will be the same length as the data you're trying to compress. It would be 0% compression in the long run.

treesprite82 6y ago
> On average, the length of the number required to point to the digit will be the same length as the data you're trying to compress. It would be 0% compression in the long run Worse than 0%. The average position of numbers 0000-9999 in pi is 9940, for example. I believe ideally you'd want a De Bruijn sequence (https://en.wikipedia.org/wiki/De_Bruijn_sequence https://en.wikipedia.org/wiki/De_Bruijn_sequence - "optimally short with respect to the property of containing every string of length n at least once") but even that won't get 1:1 compression.

anuragbiyani 6y ago

It's a commonly held misconception that Pi is proven to be normal - it is NOT (it is a conjecture as of now) [1] [2]. Proving normality of number is a very hard problem, and hardly any numbers outside of purposefully constructed ones (such as Champernowne's constant [3]) are proven normal. In fact it's not even proven that every digit occurs infinitely many times in the decimal expansion of Pi. [4] So https://github.com/philipl/pifs https://github.com/philipl/pifs is wrong in claiming that all byte stream will exist somewhere in Pi (it's not proven). Also it's worth calling out that even if Pi was Normal it will likely take more space to store the indices of two location as it will for original data itself (for at least majority of the integers), so it's not much of a "compression" strictly speaking. It's easy to see how this will work out for a known normal number - Champernowne's constant [3] -> Unlike Pi, Champernowne's constant is guaranteed to contain all the possible natural number sequences, but storing just the starting index of them in this constant is going to take much longer than the entire number itself (e.g., number "11" start at index 12 (1-indexing), number "12" starts at index 14, and so on - the size of index increases much faster than integer being looked up itself). [1] https://mathworld.wolfram.com/NormalNumber.html https://mathworld.wolfram.com/NormalNumber.html [2] https://math.stackexchange.com/a/216578 https://math.stackexchange.com/a/216578 [3] Champernowne's constant (in base 10) is the concatenation of all positive integers and treating them as the decimal expansion (following "0."): 0.12345678910111213... It can be trivially seen that it contains all natural number strings. It is also proven to be Normal in base 10 (which is a stronger property). See https://en.wikipedia.org/wiki/Champernowne_constant https://en.wikipedia.org/wiki/Champernowne_constant for details. [4] https://en.wikipedia.org/wiki/Normal_number#Properties_and_examples https://en.wikipedia.org/wiki/Normal_number#Properties_and_e...

tombert 6y ago
I know it's just a conjecture, it's actually mentioned in that Github page that it's a conjecture. That said, if we assume it's true, it's an interesting thing to think about.
- anuragbiyani 6y ago
  I was referring to the claim made in the README's section: "Every file that could possibly exist?", which is written as if it's a proven statement: > That's right! Every file you've ever created, or anyone else has created or will create! Copyright infringement? It's just a few digits of π! They were always there! But yes, after you mentioned it, I see that the conjecture disclaimer is mentioned in a section at top ("What does π have to do with my data?") and afterwards the fact is assumed as true in rest of the README.

jonny_eh 6y ago

How would that be any better than "point to a spot on the number line"?

tombert 6y ago
I suppose it's not functionally different, since any binary can be expressed in terms of an integer. My tail has been thoroughly planted between my legs.