6 ms·
Ah, without preserving order. That's a set of four 5-bit values, not a sequence of four 5-bit values.
by amptorn 9y ago
Ah, without preserving order. That's a set of four 5-bit values, not a sequence of four 5-bit values.
- deleted 9y ago[deleted]
- ajkjk 9y agoTo 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.
- Buttons840 9y agoIs there a specific topic of study that taught you those formulas?
- gpm 9y agoNot the person you asked but 4! is the number of permutations of a list - it's commonly seen throughout CS theory and other forms of discrete math. log_2(n) is the number of bits needed to store a integer from 0 to n - it's reasonably commonly used in CS theory education.
- cameldrv 9y agoProbability theory and information theory.
- SilasX 9y agoAs cameldrv said, information theory. The late David MacKay has a good free book: http://www.inference.org.uk/itprnn/book.html http://www.inference.org.uk/itprnn/book.html The intro chapters cover the topic of measuring informational entropy. Aside: One interesting application is to the problem of “use a balance scale only three times to determine which of twelve balls has the wrong weight (too heavy or light)”. You choose the weighings so as as to maximize the entropy of the outcome i.e. so there are many possible outcomes of equal probability.
- abpavel 9y agotry combinatorics branch of mathematics
- arnarbi 9y agohttps://en.wikipedia.org/wiki/Information_theory https://en.wikipedia.org/wiki/Information_theory
- ajkjk 9y agoAs 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 http://affect-reason-utility.com/1301/4/shannon1948.pdf . It's surprisingly readable and worth at least skimming if you like this stuff.
- londons_explore 9y agoYour math is wrong. If two of the numbers happen to be the same, order no longer matters for those numbers, so your log2(4!) needs to be larger...
- jack9 9y agoThe maximum entropy is what is important, to the encoding challenge, as I understood it.
- deleted 9y ago[deleted]
- deleted 9y ago[deleted]
- deleted 9y ago[deleted]
- scatters 9y agoRight. So the true answer is log2((32*31*30*29)/(4*3*2) + (32*31*30)/2 + (32*31) + (32*31)/2) = 15.675 which is still smaller than 16.
- yorwba 9y agoAre 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_multisets https://en.wikipedia.org/wiki/Bag_(mathematics)#Counting_mul... ) log2( (35*34*33*32)/(4*3*2*1) ) = 15.676
- pishpash 9y agoThe second answer, 15.676, is the correct one. It can also be arrived at by: log2(32C4 + 32C3 * 3 + 32C2 * 3 + 32C1)
- marcoperaza 9y ago[deleted]
- dboreham 9y agoThey're not ordered: that's the whole point.
- marcoperaza 9y agoMy bad, I misread!
- joshuak 9y agoHmm, it's interesting to me that order would be expected. I nearly always think of storage and ordering as entirely separate problems.
- yorwba 9y agoUsually, when you store a value, you want to be able to get exactly that value back. If you store multiple values without keeping the ordering, you lose that capability. I.e. you can't replace all possible uses of four 5-bit variables with one 16-bit variable, only those where the variables are interchangeable.
- joshuak 9y agoMany common data structures fail to preserve order. Maps (aka dictionaries) based on hash tables come to mind. Slightly adrift of the topic... I have a HAMT (hash array map trie) implementation that uses a 32-bit unsigned int as a bitfield to indicate which of the 32 possible children nodes are populated. With this trick I could encode any node with 5 or fewer bits flagged with a 16-bit unsigned int instead. I just checked and 1 million keys created roughly 1.3 million nodes (1 million keys, 300k internal nodes). Nearly 90% of the 300k internal nodes have 5 or fewer bits set. This trick would make the HAMT overhead nearly half the size. Very useful! Now, how about 6-bit values in one 32-bit value? I'd like to try this with a 64-bit HAMT. Can this be easily generalized? Edit: Oops, that should be nodes with 4 or fewer bits set, there are only 4, 5-bit values. Interestingly that apparently doesn't make much of a difference for HAMTs only about 2k internal nodes out of 300k have 5 children. So the results remain the same.
- sweettea 9y agoI believe, based on the math, that 6 6-bit values barely don't fit in 32 bits. :(
- scythe 9y agoThe number of bags of k N-bit numbers is 2^N + k - 1 choose k: https://en.wikipedia.org/wiki/Multiset#Counting_multisets https://en.wikipedia.org/wiki/Multiset#Counting_multisets The number of bits required to uniquely represent such a bag is thus ⌈log2((2^N+k-1) choose k)⌉. For (N, k) we have: (6, 6) -> ⌈log2(69 choose 6)⌉ = ⌈log2(119877472)⌉ = 27 bits (6, 7) -> ⌈log2(70 choose 7)⌉ = ⌈log2(1198774720)⌉ = 31 bits So you can store seven 6-bit integers without order in one int32. I don't know if it'll be slow, though. It should be possible to infer an encoding algorithm from the proof of the counting formula but it might be slow.
- ChuckMcM 9y agoYup so no ARGB5555 16 bit type :-)
- kuschku 9y agoBut an MSAA 4-fragment each 5-bit 16-bit type. Or MSAA4x ARGB5555 in 64-bit (instead of 80 bit)
- craftyguy 9y agoWell, the title literally says "a set of" and "not a sequence of".