# Tag Info

### Efficient compression of simple binary data

Sure, of course there are algorithms. Here is my algorithm: First, check if the file contains ordered binary numbers from $0$ to $2^n-1$, for some $n$. If so, write out a 0 bit followed by $n$ one ...
• 160k
Accepted

### Do lossless compression algorithms reduce entropy?

A lot of casual descriptions of entropy are confusing in this way because entropy is not quite as neat and tidy a measure as sometimes presented. In particular, the standard definition of Shannon ...
• 616
Accepted

### Can data be compressed to size smaller than Shannon data compression limit?

Actually I don't fully understand this algorithm or the Shannon limit very well, I just know it's the sum of the probability of each character multiplied by log2 of the reciprocal of the probability. ...
• 13.6k
Accepted

### Efficient compression of simple binary data

This seems to be a clear use case for delta compression. If $n$ is known a priori this is trivial: store the first number verbatim, and for each next number store only the difference to the previous. ...
• 1,681
Accepted

### Simulating a probability of 1 of 2^N with less than N random bits

Wow, great question! Let me try to explain the resolution. It'll take three distinct steps. The first thing to note is that the entropy is focused more on the average number of bits needed per draw,...
• 160k
Accepted

• 277k
Accepted

### PRNG for generating numbers with n set bits exactly

What you need is a random number between 0 and ${ 64 \choose n } - 1$. The problem then is to turn this into the bit pattern. This is known as enumerative coding, and it's one of the oldest deployed ...
• 22.2k

### Do lossless compression algorithms reduce entropy?

No, if the algorithm is lossless no steps in the compression sequence can reduce its entropy - otherwise it would not be able to be decompressed/decoded. However, the additional entropy may be stored ...

### Can data be compressed to size smaller than Shannon data compression limit?

You first apply the model to the data, computing the sequence of probabilities, f.e. $1/2$, $1/3$, $1/6$. Then, to encode each symbol with probability $p$, you need $log_2(1/p)$ bits. And given some ...
• 1,873

### I think you can always compress compressed data, is it true?

Here's the problem with that reasoning: If you could always compress data, you could compress the compressed data, then compress that, etc. until you have something that is 0 bytes long. You can ...
• 29.8k

• 39k

### Find the number using binary search against one possible lie

A generalization of this class of problems is widely studied. See, e.g., this paper for a survey. In your particular case, the problem can be easily solved without any asymptotic change in the ...
• 29.5k

• 277k

### Find the number using binary search against one possible lie

If normal binary search would take k questions, then you can solve this with 2k+1 questions: Ask each question twice. If you get the same answer, it was the truth. If not, a third question reveals the ...
• 30.4k

### Algorithms that achieve better compression for more data

Compressing compressed data only benefits you if the original compression wasn't very good. Good compression essentially removes all the patterns, leaving very little for any future round of ...
• 81.8k

### Arithmetic coding and "the optimal compression ratio"

Beware: The phrase "optimal compression ratio" is perhaps a bit misleading. It is intended to make you think of "the best compression ratio that is achievable", but there are some assumptions that it ...
• 160k