(www.patrickcraig.co.uk)

181 points ekiauhce | 1 comments | 23 Nov 24 21:10 UTC | HN request time: 0.213s | source

Show context

benchmarkist ◴[24 Nov 24 00:08 UTC] No.42224932[source]▶

Take random bytes from /dev/urandom, encrypt it. There is no way any compressor can reduce the size of that file. I'm pretty sure there is no way the second player can win this game. Actually, the encryption part isn't even necessary. There is no compressor that can reduce the size of a random stream of bytes.

replies(3): >>42225052 #>>42225062 #>>42225454 #

1. Retric ◴[24 Nov 24 00:35 UTC] No.42225062[source]▶

>>42224932 #

But you don’t need to compress every possible file to make playing such a game a good idea.

Suppose if you shave 1 bit off of a sample bit stream you win and you lose if that fails. Your compressor looks at the first 2 bits and if it starts 11 it starts with 1 and otherwise it starts 0 then the bit stream. Now you have a 1 in 4 chance to compress a random string by 1 bit and. A 3 in 4 chance of making it longer by 1 bit.

It’s ultimately not about compression but what odds are worth it.

↑

The $5000 Compression Challenge (2001)