Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Show HN: How to store a set of four 5-bit values in one 16-bit value

github.com

Post reply on HN
Print view View original

121–130 of 149 posts

Re: Show HN: How to store a set of four 5-bit values in one 16-bit value

#121

Post by ajkjk »

Buttons840 wrote: post #11
ajkjk wrote: post #6

Earlier quoted context omitted.

To answer the obvious next question: Four 5-bit values in order have 20 bits of entropy, so cannot be stored in 16 bits. Four 5-bit values without order have 20 - log2(4!) =~ 20 - 4.59 = 15.41 bits of entropy (corresponding to log(2^20/4!) possible configurations), and thus can fit in 16 bits of data if you're clever about it.

Is there a specific topic of study that taught you those formulas?

As others have mentioned, it comes up in information theory, or maybe in some subfields of combinatorics and probability. I learned it tangentially in various parts of physics.

But I might just recommend going to the source! which is Claude Shannon's seminal masters thesis on coding: http://affect-reason-utility.com/1301/4/shannon1948.pdf . It's surprisingly readable and worth at least skimming if you like this stuff.

Re: Show HN: How to store a set of four 5-bit values in one 16-bit value

#122

Post by bonzini »

pishpash wrote: post #86
yorwba wrote: post #60

Earlier quoted context omitted.

Are you sure you don't mean log2((32*31*30*29)/(4*3*2*1) + (32*31*30)/(3*2*1) + (32*31)/(2*1) + 32/1) = 15.34 using the number of sets of values from {0, 2^5-1} with at most 4 elements? If on the other hand you want to store exactly 4 values, possibly with duplicates (while still ignoring order), you need to count multisets ( https://en.wikipedia.org/wiki/Bag_(mathematics)#Counting_mul... ) log2( (35*34*33*32)/(4*3*2…

The second answer, 15.676, is the correct one. It can also be arrived at by: log2(32C4 + 32C3 * 3 + 32C2 * 3 + 32C1)

What the parent message did is: log2(32+4-1 C 4), because the number of k-sized combinations of n objects with repetitions is (n+k-1)Ck. One way to prove it is that you sort the objects (so you can establish an order among the objects in the combination) and add k-1 dummy objects for "the second is the same as the first, the third is the same as the second,..., the last is the same as the penultimate".

Re: Show HN: How to store a set of four 5-bit values in one 16-bit value

#123

Post by bonzini »

bubblethink wrote: post #119
pishpash wrote: post #86

Earlier quoted context omitted.

The second answer, 15.676, is the correct one. It can also be arrived at by: log2(32C4 + 32C3 * 3 + 32C2 * 3 + 32C1)

I followed the original link as well as this calculation. Why not use this to map them directly (instead of breaking it into 12 bits and 4 bits) ? We'll just have some unused headroom in 16 bits. This would seem more natural than thinking of the 12 + 4 solution.

It uses more memory.

Re: Show HN: How to store a set of four 5-bit values in one 16-bit value

#124

Post by steve_musk »

Robin_Message wrote: post #117
steve_musk wrote: post #116

Earlier quoted context omitted.

Seems impossible to me.

Try doing it with just two people. Then extend the concept somehow. All the details of the puzzle are important.

Well it’s easy to do with two people because the first person can just guess the color of the second, since we are allowed one wrong guess. I don’t see how this can be extended.

Re: Show HN: How to store a set of four 5-bit values in one 16-bit value

#126

Post by Too »

steve_musk wrote: post #124
Robin_Message wrote: post #117

Earlier quoted context omitted.

Try doing it with just two people. Then extend the concept somehow. All the details of the puzzle are important.

Well it’s easy to do with two people because the first person can just guess the color of the second, since we are allowed one wrong guess. I don’t see how this can be extended.

You can extend to three people if the first "guess" indicates if nr 2 and 3 have the same color or not. But doesn't go further because after the first all guesses must be 100% correct and can't be used for communicating additional information.

Re: Show HN: How to store a set of four 5-bit values in one 16-bit value

#127

Post by fyi1183 »

steve_musk wrote: post #124
Robin_Message wrote: post #117

Earlier quoted context omitted.

Try doing it with just two people. Then extend the concept somehow. All the details of the puzzle are important.

Well it’s easy to do with two people because the first person can just guess the color of the second, since we are allowed one wrong guess. I don’t see how this can be extended.

I assure you that it's possible. To give you a hint without giving everything away: the guess of the first person must be derived from the colour of all other person's hats.

You could think of it as a puzzle in coding theory, and it's not implausible. If you sum up the number of hats that each person sees and the number of guesses they hear, you'll note that everybody has 9 bits of information available. And they're supposed to make 9 correct guesses. It adds up.

Another hint would be to think of the case of 3 persons first. That can be done with patient case analysis, and it's likely to get you an idea for generalisation.

Re: Show HN: How to store a set of four 5-bit values in one 16-bit value

#128

Post by OJFord »

steve_musk wrote: post #124
Robin_Message wrote: post #117

Earlier quoted context omitted.

Try doing it with just two people. Then extend the concept somehow. All the details of the puzzle are important.

Well it’s easy to do with two people because the first person can just guess the color of the second, since we are allowed one wrong guess. I don’t see how this can be extended.

Think about it as if each guess preceding a person is a bit of information, the goal is to come up with a strategy for using that information (you control encoding as well as decoding) to correctly infer another bit.

Re: Show HN: How to store a set of four 5-bit values in one 16-bit value

#129

Post by AlphaGeekZulu »

Ahh, just yesterday in HN: Operation Gunman

http://www.cryptomuseum.com/covert/bugs/selectric/index.htm

Quotes:

"The data from the 6 magnetometers (i.e. 6 bits) was somehow digitally compressed into 4-bit words and then stored in a magnetic-core buffer that could hold up to 8 such 4-bit data words." "It is unknown why and how the data was compressed from 6 to 4 bits, and the NSA report is very vague on this point. It is possible that the Soviets used 4-bit logic and had to spread the 6-bit data over more than one 4-bit data word, but it is more likely that they used frequency analysis"

"According to the NSA report, the Russians compressed the 6-bit data into a 4-bit frequency select word. Although the report doesn't explain what they mean by this, we can make a few educated guesses. The reason for compressing it into 4-bits, was probably the fact that the Russians only had access to 4-bit digital technology at the time. The problem with 4 bits however, is that each data word has just 16 possible combinations"

...

Maybe a similar "hack"?

Re: Show HN: How to store a set of four 5-bit values in one 16-bit value

#130

Post by pm215 »

andromeduck wrote: post #91
anonu wrote: post #55

What's the practical use for this?

Saving space in data structures that use buckets such as hash tables. I actually discovered this in a paper on hash tables that kind of just mentioned that it was a thing but I had a harder time finding out exactly how it was done.

Perhaps you could mention the motivation for the trick in the readme? My initial reaction was "either this is an april-fools style joke, or it's a cute but pointless trick", and it wasn't til I got to the bottom of the HN comments that I found an explanation of why it would be worth knowing...
Post reply on HN