Hacker News Reader

Hacker News

Comment by cellular | Hacker News Reader

Parent Full thread

cellular

Maybe everyone should compress the 1st 100MB worth of digits of pi, for an apples-to-apples comparison?

Edit: oh wait that's too easy. Need to generate /publish random digits so everyone can use it.

View on HN

Compressor: Output an empty file.

Decompressor: Take any old algorithm for finding digets of pi, find first 100M of them, print them.

Compression ratio of 0! :0

random digits aren't compressible though?

Random digits are compressible though.

Random data does not mean it does not match a pattern in your dictionary for example.

No.. they're not. Do you understand random (the apparent or actual lack of definite patterns or predictability[0]) or compression (reduces bits by identifying and eliminating statistical redundancy[1])?

[0]: https://en.wikipedia.org/wiki/Randomness

[1]: https://en.wikipedia.org/wiki/Data_compression

I could write a program to generate the first 100MB of pi in a couple kilobytes. That certainly counts as “data compression” but isn’t useful outside this particular problem instance.

Yeah, because the digits of pi aren’t random.

Over infinite runs, you can't compress random data, but that doesn't mean any finite string of random digits is incompressible

by this definition, a random dataset could apparently present no patterns, while presenting non apparent patterns.

Sounds like presenting no patterns, apparently or otherwise, would be a pattern in itself.

That's like a teenage "i am very smart" thinking. I mean sure we can look at some string of random bits and say "that looks random" but you can't just generate any old string of random bits to replace it (which would be the only 'pattern' that could be leveraged for compression here). If it's encrypted it'll also appear random, and therefore not be compressible, but you have to encode every byte exactly or the message won't be decryptable.

Reply on news.ycombinator.com