7
$\begingroup$

I saw this project on github https://github.com/philipl/pifs, where they are trying to compress files in the pi number after the decimal. I guess this makes sense because apparently every finite sequence of digits exist in the never ending decimal numbers of pi. But I am trying to understand 1 step of their process.

So firstly from what I understand, if you want to compress a file, that is really represented in a sequence of numbers like say 471947...2846 (somehow gotten from base 16). Then, they assume that sequence is somewhere in pi.

They somehow then look up where the sequence starts in pi. This is the step I don't understand how they do. But they use a formula called Bailey–Borwein–Plouffe formula to do it.

So the compression is really two numbers $<A,B>$, where A is the index of the start number of pi, and B is the length needed.

To uncompress, its just a for loop, loop through every index from A, and repeat B times, and use that formula, to get the pi digit value, then convert it back to binary, and you have the original file again.

But it's that first step to find that initial start index using the formula I don't understand how that's done. Surely they don't brute force and try every combination in a linear fashion.

Does anyone know?

Thanks

$\endgroup$
  • 7
    $\begingroup$ It is not known whether every finite sequence of digits appears in the decimal expansion of $\pi$. The situation is no better for any base. $\endgroup$ – André Nicolas May 4 '16 at 20:09
  • $\begingroup$ So does that mean that github project is under the wrong impression, where they think every finite sequence exists somewhere in pi, but really it is not proven that every finite sequence exists somewhere in pi? $\endgroup$ – omega May 4 '16 at 20:11
  • 1
    $\begingroup$ It is not implausible that every finite sequence occurs, that is the case for "most" real numbers. $\endgroup$ – André Nicolas May 4 '16 at 20:13
  • 2
    $\begingroup$ They are kidding. Assume you want to code a $10$ digits number. If the digits of $\pi$ are random, you can expect to find this number at the $50$-billionth decimal (imagine that the decimals are the sequences of $10$ digits numbers, on average yours is halfway.) Think of the computing time ! And that's not all, storing the position of your number will take... $10$ digits. $\endgroup$ – Yves Daoust May 4 '16 at 20:30
16
$\begingroup$

The project you've found is a (deliberate!) joke.

It is true that $\pi$ is suspected to be normal in all bases, which would imply that every finite sequence of hex digits appears somewhere (indeed, many times) in the hexadecimal expansion of $\pi$.

But this cannot be used for compression -- the trouble is that the number $A$ that tells you where to find your file in $\pi$ will -- in the vast majority of cases -- be so large that storing $A$ takes up even more space than it would take to store the original file.

The BBP formula is not particularly suited for finding a particular sequence in $\pi$, except by trial and error, or by starting somewhere in $\pi$ and keep producing digits until you randomly come across the sequence you're looking for. So at first, the goal of the project would be completely impossible -- just locating a ten-byte file would take lifetimes. (That is, some multiple of the lifetime of the universe).

The kicker is in this part of the description:

Now, we all know that it can take a while to find a long sequence of digits in $\pi$ 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 $\pi$.

So it doesn't actually "compress" anything -- it just stores, for each byte in the file, a position in $\pi$ where that particular byte can be found. (And finding such short a segment is certainly doable by brute force). But storing such a position takes more than a byte. So all in all it's just a simple substitution code, with a particularly inefficient implementation.

(And then there's some further joking around, claiming that the indices don't count as space used because they're "metadata".)

$\endgroup$
  • $\begingroup$ This is a good answer. But I don't think "in the vast majority of cases" is true. I would expect that $A$ would be at least as large (asymptotically) $e^{-1/16}\approx93.9\%$ of the time using hexadecimal, and so 6.1% of the time you come out ahead. (Obviously, you can't capitalize on this to shrink losslessly on average, since sending a bit to say if you're using the scheme or not obviates the benefit.) $\endgroup$ – Charles May 4 '16 at 22:27
3
$\begingroup$

The Bailey-Borwein-Plouffle formula does not allow you to find a desired sequence of digits in $\pi$. As the Wikipedia page says, it allows you to find the hex digits starting as a desired place without calculating the preceding ones. So if you want the digits of $\pi$ starting at the billionth, this is your friend. This would be used in the decryption step.

It is not proven that every digit sequence appears in $\pi$, but it is likely. I am not aware of any way besides brute force to find were a given sequence occurs. The problem with the idea is that the index for your file is likely to be as long as the file. Yes, instead of storing your file you store the index, but it is just as large and harder to use. Suppose you have a file that is $1000$ hex digits long. There are $16^{1000}$ sequences of $1000$ hex digits, so you would expect your string to occur somewhere around position $16^{1000}$, which takes $1000$ hex digits to store. At this page you can search the first $200,000,000$ decimal digits of $\pi$ for a desired string. If you look for $12345678$, it reports that it occurs at position $186557266$, which is $9$ digits instead of $8$

$\endgroup$
  • $\begingroup$ Cool search. I searched for 314159 and it was found at $\pi[176451]$. $\endgroup$ – mvw May 4 '16 at 20:51
  • $\begingroup$ Fun side note: We used that search page for a contest on pi-day, we searched for the birthdays (dd/mm/yyyy), whoever came first in the digits of pi won a bottle of pi-wine! Also, if I remember correctly, it is not even known whether the number $7$ occurs infinitely many times in the digits of pi. $\endgroup$ – Mathematician 42 May 5 '16 at 9:32
1
$\begingroup$

They somehow then look up where the sequence starts in pi. This is the step I don't understand how they do. But they use a formula called [Bailey–Borwein–Plouffe][1] formula to do it.

Yes, that is a fantastic discovery, it allows to calculate the $k$-th digit behind the period without needing to know the prior digits.

This would benefit the decoding process.

That is the grain of truth behind this project.

However

They said 100% compression was impossible? You're looking at it!

and

So I've looked up my bytes in π, but how do I remember where they are?

Well, you've obviously got to write them down somewhere; you could use a piece of paper, but remember all that storage space we saved by moving our data into π? Why don't we store our file locations there!?! Even better, the location of our files in π is metadata and as we all know metadata is becoming more and more important in everything we do. Doesn't it feel great to have generated so much metadata? Why waste time with old fashioned data when you can just deal with metadata, and lots of it!

which is obviously a hoax.

Here it is likely that the index or the combined index and length result in a very large integer, probably much larger than your original file. Not a desirable feature for a compression scheme.

$\endgroup$

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.