3 ms·

A variation on this would work, but alas we don't have the math tools as yet. The idea (not mine) is that you can think of data as "very large numbers". So a 4

A variation on this would work, but alas we don't have the math tools as yet. The idea (not mine) is that you can think of data as "very large numbers". So a 4096 bit number is just a big number. Well, we have a short way to generate big numbers. x^y. So given a big number (say 800 000 bits) we could generate a (Hopefully short) expression of the form a^b + (or minus) c^d + ... etc. Unfortunately the "factorizing" (and indeed ecpansion) of a large number in this way can't (currently) be done quickly. But in concept enormously large binary files could be compressed to tiny strings.

kstrauser 1y ago
It would not work for arbitrary inputs. See the pigeonhole principal: you can’t represent all possible n-bit values with fewer than n bits, because otherwise you’d have at least one case where multiple input values map to the same output value. On decompression, which one do you go with? And if that’s not convincing, then consider that any perfect compression scheme would be able to compress its own output even smaller, until you end up with a single bit output for any possible input. So no, that wouldn’t work in general. Some specific values may compress well, but most others can’t. It’s not a matter of difficulty of finding the right answers, as much as you probably can’t do it.
- pverheggen 1y ago
  To add to this, useful compression algorithms exploit patterns in the input data. A common pattern to target is repetition, since most files contain lots of repeated byte sequences. The pattern that factorization targets are numbers that factor well. I doubt this is a pattern you’d find in any file worth compressing, it doesn’t have a clear relationship to file data.
- kstrauser 1y ago
  Amendment: autocorrect changed “provably can’t do it” to “probably” above. It’s not probable. It’s certain.
vlovich123 1y ago
Aside from the factorizing cost, I suspect decompression will also be prohibitively slow. Exponentiation, multiplication and addition such large range numbers could still end up prohibitively expensive.
- jibal 1y ago
  In addition to the performance problems there's the basic fact that no such scheme can possibly work (as proven by the pigeonhole principle). High compression rate schemes that actually work compress high likelihood inputs and expand low likelihood inputs by accounting for the characteristics that make inputs high likelihood--e.g., redundant highly patterned texts. Schemes that are agnostic about the input, like the one described here, are as likely to expand any given input as they are to compress it.
  - vlovich123 1y ago
    That’s correct. I’m a little sleep deprived at the moment but that’s definitely the mathematical reason it’s not even feasible to begin with.
deleted 1y ago
[deleted]

kstrauser 1y ago

It would not work for arbitrary inputs. See the pigeonhole principal: you can’t represent all possible n-bit values with fewer than n bits, because otherwise you’d have at least one case where multiple input values map to the same output value. On decompression, which one do you go with? And if that’s not convincing, then consider that any perfect compression scheme would be able to compress its own output even smaller, until you end up with a single bit output for any possible input. So no, that wouldn’t work in general. Some specific values may compress well, but most others can’t. It’s not a matter of difficulty of finding the right answers, as much as you probably can’t do it.

pverheggen 1y ago
To add to this, useful compression algorithms exploit patterns in the input data. A common pattern to target is repetition, since most files contain lots of repeated byte sequences. The pattern that factorization targets are numbers that factor well. I doubt this is a pattern you’d find in any file worth compressing, it doesn’t have a clear relationship to file data.
kstrauser 1y ago
Amendment: autocorrect changed “provably can’t do it” to “probably” above. It’s not probable. It’s certain.

vlovich123 1y ago

Aside from the factorizing cost, I suspect decompression will also be prohibitively slow. Exponentiation, multiplication and addition such large range numbers could still end up prohibitively expensive.

jibal 1y ago
In addition to the performance problems there's the basic fact that no such scheme can possibly work (as proven by the pigeonhole principle). High compression rate schemes that actually work compress high likelihood inputs and expand low likelihood inputs by accounting for the characteristics that make inputs high likelihood--e.g., redundant highly patterned texts. Schemes that are agnostic about the input, like the one described here, are as likely to expand any given input as they are to compress it.
- vlovich123 1y ago
  That’s correct. I’m a little sleep deprived at the moment but that’s definitely the mathematical reason it’s not even feasible to begin with.

deleted 1y ago

[deleted]