Is this a general compression algorithm?

Question

I'm aware that an algorithm that compresses every input doesn't exist (by the pigeonhole principle), however I tend to think about the problem sometimes and I came up with a (flawed, but why?) idea:

Suppose a file, or whatever it is that will be compressed. It can be represented with a number (we can actually invert the bits if the first binary digit of the file is one, and indicate whether we've flipped them or not, since computers work based on bytes, but that is detail) if we treat its bits as the base-2 representation of the number. Let such number be $n$.

It is computationally cheap ($O(\log{n})$) to find $floor(sqrt($n$))$.

We find $x_1 = floor(sqrt(n))$ and then take $y_1 = n - (floor(sqrt(n)))^2$. Then we do it again (this time, taking $floor(sqrt(y_1))$, where $y_1$ is the new value we obtained from the subtraction) and again until we have expressed $n$ as a sum of perfect squares, following that rule. Something like $x_1^2 + x_2^2 + ... + x_w^2$. We know, since we are at least dividing $n$ by two every step, that $w$ is of order $\log(n)$.

Noting that $x^2$ is equal to the sum of the first x odd numbers, we then express the squares, logically, to better understand the idea, as shown in the image:

The first line of the image represents the first square obtained from the process, the second line represent the second square obtained and so on. A random representation was chosen just to illustrate, but imagine the polygon as being the representation of any number. If we are able to precisely determine the polygon for a given $n$, we know $n$. Notice once we represent the numbers this way, we can group them in the following order:

The first red rectangle is the product of ($1+3+5$) = $(3^2)$ by however many lines the rectangle occupies. The second one is the product of ($(1+3+5+7+9+11)-(1+3+5)$) = $(6^2 - 3^2)$ by however many lines the rectangle occupies, and so on. The green square, which represents the one (may or may not exist in a given $n$ representation), is a special case.

Abstracting a bit more, given the following image:

If we know the purple points, we know the figure and, thus, we know $n$. In order to specify the purple points, we need to specify the distances in blue and the distances in brown. The vertical side of the polygon is of order $O(\log(n))$, since it is related to how many initial squares we had. The vertical side, on the other hand, is of order $O(sqrt(n))$, since they're related to $sqrt(n)$ (the representation of the square root).

What is particularly interesting, however, is that by specifying this first purple point, we are able to, in fact, infer all the other purple points and all the other brown vertical distances, provided we have registered the purple horizontal distances. To see this, imagine we are in the first brown point. We then see the next horizontal distance and are able to know exactly the next vertical distance (and consequently the brown point); we know how the pattern continues. We know how many lines we have total, since we are able to "see" the first red rectangle (and the green square if we specified it or not). We further know that the vertical distance between one point and the next point is always one, due to the fact that no two lines are equal (since they represent different squares). Point is, given the basic representation of the first vertical distance, we know all the vertical distances.

Maybe it is possible to represent the first brown distance with fewer bytes increasing its exponent or tweaking it somehow. I had an idea in mind but I just realized it's flawed. And the blue distances would need to be represented (they can be taken as a new $n$ and all the process repeated again).

Also, it's worth noting that the the horizontal distances relate to the previous horizontal distances because when we made the squares for $n$, the subtraction $n - floor(sqrt(n))^2$ is taken as the new $n$, and is represented as $x_m$, but $n - floor(sqrt(n))^2$ is always between $1$ and $2floor(sqrt(n)) - 2$ (if it were 0, it would be a perfect square, so great; if it were $2floor(sqrt(n)) - 1$, it could be integrated into $x_m^2$, so it can never be that (nor greater than that)).

Anyhow, I am sorry if the explanation is a bit messy. I just had to share my ideas and ask whether it's worth implementing something related to the idea above in order to test it, or it is a waste of time. That is, if the approach is good (most likely, perhaps impossibly likely, as said in the beginning, to not be the case). Thanks! Edit: it is proven to be impossible to compress every input, what I meant to ask was whether this approach would be useful for most of the inputs or thoughts on the approach in general and why it doesn't work.

Answer 1

At its core what you propose is splitting a number $n$ into two, a square part and a remainder:

$$s=\lfloor\sqrt{n}\rfloor, \quad\quad r=n - s^2$$

Encoding $s$ requires $\log_2(s) = \log_2\lfloor n^{1/2} \rfloor \approx \frac{1}{2}\log_2 n$ bits. And as you said, $$1 \leq r < 2s$$ thus we can say that in the worst case $r$ requires $\log_2 r \approx \log_2(2s) \approx 1 + \frac{1}{2}\log_2 n$ bits to encode.

So in total we're actually roughly one bit worse off in the worst case. Note that the above is kind of sloppy, but should give you an intuition as to why it doesn't work. If you want to prove that it doesn't give you general compression, just use the pigeonhole principle - it's much simpler.

Answer 2

The information theoretic argument -- the so-called pigeon hole principle -- also shows that it is impossible to compress "most" inputs. You can only compress a minority inputs, and the fraction of successfully compressed inputs decreases with increased compression.

Suppose we were compressing bit sequences of length $N$. There are $2^N$ such sequences. As a very modest goal, we'll just compress the sequences by one bit, so that the compressed result has $N-1$ bits. But there are only $2^{N-1}$ different sequences of $N-1$ bits. So half of the original sequences cannot be represented with $N-1$ bits. Since we have to be able to represent any possible input, at least one of the $(N-1)$-bit sequences must be the prefix of longer encodings, and thus is not usable as a compressed code. So the number of compressed sequences must be less than half of the total number of possible inputs. And that's a compression system with miniscule compression.

An important aspect of the above is that bit sequences do not have an intrinsic length. If the sequence is variable-length, the length must somehow be encoded, adding to the length of the encoded sequence.

Or in a possibly more intuitive sense, you cannot encode a single number into a list of smaller numbers without also accounting for the commas (or whatever) which separate the numbers in the list. Without commas, you couldn't know whether 234 represented 23,4 or 2,3,4. So you can't say that the encoded list is just three digits long.