Are there any compression algorithms based on PI?

Question

What we know is that π is infinite and quite likely it contains every possible finite string of digits (disjunctive sequence).

I've seen recently some prototype of πfs which assume that every file you've created (or anybody else) or you will create, it's already there so it's a matter of extracting it. There is also piFile which can convert your files to pi metadata.

There is already BBP type formula (as part of experimental mathematics) which allows us to compute nth binary digit of pi. So storing position of our start and length of the data, we can theoretically extract the data of our interest. There are some arguments against it that our metadata (e.g. the offset to our data) could be larger than the extracted data. The matrix symbols and π can be encoded in base-256 to make it more efficient (see the joke).

Based on above, my main question is:

• Are there any compression algorithms based on PI?

If not, does it make sense? Or were there any researches in that area?

Or maybe π is not the right one, so what about Euler's constant or Tau (τ)? Would it make any difference?

---

^{Image credits: Dinosaur Comics}

---

See also:

• Can any finite bit string be found in pi within a reasonable amount of time? at SO
• Wouldn't storing the index into π be as big (or bigger) than the original data? at GitHub

Answer 1

Your suggestion doesn't make much sense, for many reasons. First of all, when trying to compress a large file, say a file of size $16$ bytes, you will have to find a place in the binary expansion of $\pi$ which agrees with your file. Since the file is $128$ bits long, one would expect this place to be around the $2^{128}$th bit. So it would be rather hard to find. This is not only because we have to go far into the expansion, but also since we expect to try $2^{128}$ different locations before finding a hit.

Second, while in some cases your scheme will result in a major compression, this will only happen when a certain string appears comparatively early in the expansion of $\pi$. There is no reason you would ever want to compress that sort of string. In contrast, other compression algorithms try to find structure in the data, and have guarantees that show that if such a structure exists, then they can always exploit it.

Changing $\pi$ with any other number wouldn't change the picture. The algorithm is too specific, compressing only strings we aren't really interested in; and very inefficient in the compression phase.

Answer 2

Based on Yuval's answer, with a slightly different explanation and an example to help illuminate the problem.

Theory

Take a file $16$ bytes long ($128$ bits). The compression algorithm follows:

1. Determine where the binary expansion of $\pi$ matches the contents.
2. Store the offset and number of sequenced bits ($128$).

The offset for the file contents should be around the $2^{128}$^th bit; however, it is time consuming to find the offset because it requires:

• a deep search for the bit pattern; and
• looking at $2^{128}$ different locations (on average).

Matches that occur early enough in $\pi$ to attain significant compression will not be varied. That is, it isn't possible to use $\pi$ to compress interesting, real-world data because real-word strings are unlikely to arise early.

See also, information entropy.

Example

Let's compress a social security number (SSN): 938-933-556. Calculate the number of bits to encode that value using $log_2(938933556)$, which is ~$29.8$ and must be rounded to $30$ (as bits are indivisible).

In $\pi$, that SSN starts at offset $597,507,393$, which needs $log_2(597507393)$ bits, or ~$29.2$ and must also be rounded to $30$. There might be an earlier offset, but it is unlikely to require significantly fewer bits.

Maybe we can chunk the numbers?

• 938, offset $1,124$, 11 bits
• 933, offset $1,216$, 11 bits
• 556, offset $11,727$, 14 bits

That's $36$ bits, an even worse result. Perhaps a different chunking?

• 9,389,335, offset $15,312,393$, 24 bits
• 6, offset $8$, 3 bits

That's $27$ bits, which is better than $30$, but has problems. First, the addition of a non-uniform chunking requires more information to indicate where the chunks start and stop. Second, it is even more time intensive to find the optimal chunking to attain the fewest bits. Third, saving three bits barely qualifies as compression.

Different transcendental numbers will have the same statistical result, more or less. Even if you shave off a hair, say, two bits' worth, the constant that was used must be indicated. Three bits allows the algorithm to select from one of eight different numbers. As a consequence, the algorithm would be much slower due to searching $N$ sequences instead of one.

Answer 3

Are there any compression algorithms based on PI?

yeah, https://github.com/divinity76/pi_compression

does it make sense?

nope, storing the offsets typically takes more disk space than you save, at least with the above implementation (3 notable things about it that could be improved though, it only considers the first 2^32 bytes of a binary representation of pi, and it uses an excessive amount of bits to store the number of matching bytes per offset, namely 8 bits while testing shows that 3 bits would be optimal, and it only considers full-byte-matches, so if there's a 15 bits match somewhere, it will only be considered as a 8 bit match.. also if the last 4 bits of a byte matches but not bit #3, and the first 4 bits of the next byte matches but not bit #5, it's not considered to be a match at all)

Or were there any researches in that area?

uhm sure, that's why i wrote the above implementation, and the results seem to be that within the first 4GB of pi, you're likely to find 4 matching bytes of.. pretty much anything, which is very difficult, if not impossible, to gain any compression out of, i failed at least. (but my implementation is not optimal, as explained above) - also the compression is very slow, but my implementation is single-threaded, but the algorithm allows for multithreading if someone could be arsed writing the code, which would allow for scaling performance with the number of available cores.

decompression is very fast, though.

Answer 4

Are there any compression algorithms based on PI?

this question seems to be motivated by the idea that there is some "popular science" speculation that $\pi$ or other math constants contain all possible sequences of digits, but it is unproven. a compression algorithm based on $\pi$ having arbitrary sequences of digits is not inconceivable but would hinge on the following property. ie "afaik" its an open problem/ question whether the following question is (un)decidable (and the same holds for other classic constants):

input sequence $X$. output, Y/N, $\pi$ contains the sequence $X$

there are not "mainstream" compression algorithms based on $\pi$ but in (T)CS its difficult/ problematic to draw a strict boundary around "mainstream". in contrast to popular usage of the term, referring to a set of "widely used" or "standard" algorithms, a "compression algorithm" in CS is a very broad concept. technically yes, "a compression algorithm based on $\pi$ exists", because it is easy to construct a "contrived" one (exercise to reader), but no, no standard algorithms are based on sequences of digits in mathematical constants.

even if any math constant was shown to have the remarkable property of "containing all strings", a simple argument is that the compression algorithm would spend "too much time" searching for the position of the string, and describing its location would often take a long(er) string of digits.

see also/ contrast/ try to reconcile with similar high-voted question how can it be decidable whether pi contains some sequence of digits. (cs.se) (hint: the title can be regarded as somewhat misleading)