Non-lossy compression implications

[Canadjun]

There’s a simple reductio ad absurdum argument to show that not all strings can be compressed in a loss-less fashion.

Assume the contrary. Compress the string. It must be at least one bit shorter or you couldn’t say you had compressed it. Now compress the compressed string. Repeat as many times as there were bits in the original string. You have now compressed the entire string down to one bit in a loss-less fashion. Since all those steps were loss-less, you should now be able to expand that one bit back into the original string. How do you propose to do that?

[Chronos]

However to do so I had to set up several 1,000 place arrays to store the intermediate figures. (can it be done without it?)

There’s no known way, in base 10. But a few years ago, someone found an algorithm for generating the nth base-2 (or any base that’s a power of 2) digit of pi, without having to store all the others.

Of course, the fact that a base-10 algorithm still requires loads of memory doesn’t change the fact that the digits are still highly compressible. The decompression is very difficult, sure, but it’s possible in principle.