12 ms·
Show HN: How to store a set of four 5-bit values in one 16-bit value
- amptorn 9y agoAh, 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".
- raphlinus 9y agoThis is quite related to the problem of sorting a million 32 bit integers using only 2M of RAM (and no disk). It can be done.
- 6nf 9y agoOnly if all your ints are unique I guess?
- raphlinus 9y agoNo, that's not a requirement, as it turns out, though of course it would decrease the entropy even further.
- londons_explore 9y agoIf I only have 8 bytes of ram and a program counter I can do it... For (I=0; I<1<<31; I++) For (J=0; J<1e6; J++) If (input[J]==I) print(I); Shoddy runtime, but hey...
- raphlinus 9y agoYes, this is a problem that requires careful specification. You only get streaming access to your input, not random.
- andromeduck 9y agoCouldn't you just do that with radix sort or am I missing something?
- raphlinus 9y agoYes, you're missing something. Radix sort, like most sorting algorithms, requires storing the intermediate results in memory. This problem seems impossible at first blush because storing 1 million 4-byte integers would seem to require 4M of RAM, and only 2M is available.
- bringtheaction 9y agoThat is one big-ass makefile though. I realize it has some extra niceties but I have to ask, did you ever try make main without any makefile at all? If you haven't done so, delete the makefile now (you have it in version control anyway) and give it a try.
- torstenvl 9y agoGNU Make has a number of implicit rules. A blank target rule (or no target rule) in the Makefile (or no Makefile at all!) will cause `make` to try to create the specified target `foo` from `foo.c` or `foo.cpp` (or others) if they exist. More complete explanation here: https://www.gnu.org/software/make/manual/html_node/Catalogue-of-Rules.html#Catalogue-of-Rules https://www.gnu.org/software/make/manual/html_node/Catalogue... Note: I was initially annoyed with parent's "do this and see what happens" post and its lack of substantive communication, and responded poorly. This comment is substantially edited.
- bringtheaction 9y ago> self-impressed and coy That's an odd thing to read into my comment. I am merely passing on information that was at one point given to me when I myself had a Makefile that was actually not needed because the program it was for was a single source file project like OP. Also in what way is it easier to read a long document without reference to a specific section than it is to just delete the makefile and run make and the stem of the name of the source file? Edit: My second paragraph of this comment was written prior to parent commenter editing their comment.
- yorwba 9y agoI appreciate that you edited your comment to make it more informative. Now if you could also remove the snark, it would be a great comment.
- torstenvl 9y agoThere is no snark. I think the GGP's post adds nothing of value, and is in fact rude. It's not snark to point that out, anymore than your critique of my post is snark. You may feel differently. That's fine. But differing opinions being downvoted to oblivion is ... problematic, at best. EDIT: After reading your response below, you were right and I was wrong. Editing.
- barrkel 9y agoThe fact that it's using lookup tables to store the mapping between the set of numbers and the encoded 16-bit number makes it less interesting; it basically just enumerates the set of all possible combinations of numbers, and uses the ordinal as the encoding. A directly calculated scheme without a lookup would be niftier, though I suspect in practice the way it steals bits from redundancy of duplicates it wouldn't be pretty.
- hinkley 9y agoIt does seem like it should be calculable without the lookup table. Something with modular math perhaps.
- LukeShu 9y agoI had to add `#include <algorithm>` to get it to compile.
- psyc 9y agoThis is a great little lesson in information entropy. I work on similar problems quite often in my work, and understanding this was a pleasant epiphany.
- uiri 9y agoConversely: the order for 5 4-bit values itself has 4-bits of information.
- olympus 9y agoThe order for five four bit values has about 6.91 bits of information. log_2(5!)=6.91 More relevant to the problem, the order for four five bit values has about 4.59 bits of information (log_2(4!)=4.59). Not all of the sets actually have four numbers- many have duplicate numbers, like the list [1 1 2 3] is a set of numbers {1 2 3}- and that gets us down to 4.08 bits of information which is small enough to make this example work. At least that's how I understand this. I could be wrong.
- deleted 9y ago[deleted]
- nightcracker 9y agoIt is possible to do this in O(1) memory, for arbitrary sized collections, efficiently. The first trick is to make a function that can calculate the nth set with k elements from some universe U (in this case U = {0..2^5-1} without order (no duplicates) directly. This is done using the https://en.wikipedia.org/wiki/Combinatorial_number_system https://en.wikipedia.org/wiki/Combinatorial_number_system. This is very efficient. Then, to encode duplicates you use the stars and bars trick.
- scythe 9y agoI'm pretty sure that computing N choose k requires O(k log N) memory to store the result (for N >> k). Neat trick though.
- nightcracker 9y agoI should've said O(small), I'm comparing to the solution in the OP, which computes all possible combinations in a lookup table.
- tveita 9y agoArithmetic coding will work too, without any special trick to code duplicates.
- nightcracker 9y agoI don't believe that it does, at least not without some additional trick. How do you handle the case where you repeatedly encode the largest case? E.g. {31, 31, 31, 31}.
- rafael859 9y agoCan you elaborate? I am not very familiar with arithmetic coding, but I thought it required arbitrary precision floating point numbers, so not O(1) memory.
- tveita 9y ago
- sabujp 9y agohow are you getting 3876 unique values for a set of 4 4 bit values (16, 16, 16, 16) ?
- yorwba 9y agoIt's not the number of sets with at most 4 elements (which would be 1820), it's the number of bags with exactly 4 elements (i.e. the multiplicity of duplicate elements matters). https://en.wikipedia.org/wiki/Bag_(mathematics)#Counting_multisets https://en.wikipedia.org/wiki/Bag_(mathematics)#Counting_mul...
- jandrese 9y agoHe doesn't care about the order so 1, 2, 3, 4 is stored the same as 4, 3, 2, 1. That's where the savings is coming from.
- lostatseajoshua 9y agoI really don’t understand why not caring about the order would save space. Could you explain in simple terms please?
- pavlov 9y agoConsider the simplest case where your set members are just bits. If you have three bits and you care about the order, that's a 3-bit number -- it can take 8 different values. If you have those same bits but you don't care about the order, the operation is a "bit count" -- you can only have 4 different values.
- jandrese 9y agoIf you care about the order then 1, 2, 3, 4 has to be stored differently than 4, 3, 2, 1, as well as 1, 3, 2, 4, and so on. If you don't care about the order all of those can be stored in exactly the same way. Think of it like lossy compression, if you don't care about some of the detail you an ignore it (the order of the numbers in this case) and save some space.
- 9y ago
- grawprog 9y agoIt's pretty cool and all but what are the uses for this? What set of 4 un ordered 5-bit numbers would i need to store that I couldn't just store as 3 bytes? I waste only 4 bits while preserving the order if need be of the values I'm storing. I can think of a very very small few occasions 4 bits would matter over order but nothing realistic. Again It's a cool trick and I'm not trying to be a dick about it. I like cool little tricks like this even if there's no purpose. I'm honestly curious about some realistic use cases for this or some variation of this with larger numbers.
- joshuak 9y agoIt's 4 5-bit values, not 5 4-bit values. 5-bits is enough to enumerate each bit in a 32-bit bitfield. This means for any application that might set 4 or fewer flags out of a possible 32 need only use a 16-bit bitfield. As I said in another comment I just tested this with a 32-bit hash array mapped trie, and it would result in a significant reduction in the storage overhead of the trie (which is already more efficient than typical hash tables for map like data structures).
- anonu 9y agoWhat's the practical use for this?
- andromeduck 9y agoSaving 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.
- joshuak 9y agoAny chance you can remember which paper?
- andromeduck 9y agohttps://www.cs.cmu.edu/~dga/papers/cuckoo-conext2014.pdf https://www.cs.cmu.edu/~dga/papers/cuckoo-conext2014.pdf
- pm215 9y agoPerhaps 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...
- andromeduck 9y agodone :)
- yshklarov 9y agoTaking this to the extreme, you could "store" 65535 1-bit values in one 16-bit value. You just have to keep track of how many of them are equal to 1.
- uniformlyrandom 9y agoThank you - this is a much better explanation of how this 'storage' works.
- ViktorV 9y agoI think this is not true for single bits this way.
- ttoinou 9y agoCould one practical use of the general case be to store factorial based numbers efficiently ? https://en.wikipedia.org/wiki/Factorial_number_system https://en.wikipedia.org/wiki/Factorial_number_system
- rasen58 9y agoWhy is this first line true: "This works because there are 3876 possible unique values for a set of 4 4 bit values" Each 4 bit number has 16 possible values. And you can order them in the set in 4! = 24 ways. So I thought you would get 24 * 16 = 384. Can someone explain?
- karlding 9y agoThey're taking the multiset [0]. So it's \binom{2^4 + 4 - 1}{4} = 3876 In other words, there are 3876 multisets of cardinality 4 with elements taken from the set containing all 4 bit values. [0] https://en.wikipedia.org/wiki/Multiset https://en.wikipedia.org/wiki/Multiset
- rasen58 9y agoCan you explain the top number (2^4 + 4 - 1)? I understand the bottom number 4 is probably because you're choosing 4 values out of the set of numbers from the top, but not sure how you got 2^4 + 4 - 1.
- utopcell 9y agoThe title is deceptive. It should state that the goal is to store a set of four 5-bit values.
- utopcell 9y agoFor completeness: The number of possible sets that include 4 numbers from the range [0..15] is (16+4-1) choose 4, or 3876. Let's assume that our set is (a, b, c, d). It is ordered, therefore a <= b <= c <= d. For example, a valid set is (2, 4, 4, 10). Consider all possible numbers that may be in our set, laid out in order. 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 For each element in the set, we mark its position in this order by placing a marker to the left of the corresponding number. For our example, we first mark element 2: 0 1 m 2 3 4 5 6 7 8 9 10 11 12 13 14 15 Then 4: 0 1 m 2 3 m 4 5 6 7 8 9 10 11 12 13 14 15 Then, 4 again: 0 1 m 2 3 m m 4 5 6 7 8 9 10 11 12 13 14 15 And finally, 10: 0 1 m 2 3 m m 4 5 6 7 8 9 m 10 11 12 13 14 15 Now, out of these 16+4 places, only 19 of them could be a valid placement for a marker, as a marker should always be placed to the left of a number (or said differently, "15" will always be in the end.) Therefore, there are 19 choose 4 ways to pick the locations of the markers.
- shaklee3 9y agoThanks. That was really helpful.
- mgelbart 9y agoI wrote a blog post several years ago that's basically about this same effect, although from a different angle: https://hips.seas.harvard.edu/blog/2013/06/05/compressing-genomes/ https://hips.seas.harvard.edu/blog/2013/06/05/compressing-ge...
- RandomCSGeek 9y agoI haven't learned about compression of data, but from what I know, one has to make some assumptions to store n bit data into m bit space, where m < n. Here, the assumption seems to be that numbers are necessarily 5 bit, and that there are only 4 numbers. What I fail to understand is how this helps to compress the data in this case. The code isn't really that nice, and the comments seem to assume prior knowledge is this field, which I don't have. So can someone give a ELI-Noob?
- SilasX 9y agoIt’s not perfect compression; it’s lossy. Per the top comment, this method treats it as a set i.e. ignore the order. So you’re throwing out some information. https://news.ycombinator.com/item?id=16249092 https://news.ycombinator.com/item?id=16249092
- lostatseajoshua 9y agoCan someone explain this in very simple terms without math? An ELI5 example. Thank you.
- hinkley 9y agoIf you’re playing Yahtzee or cards it doesn’t matter what order you get the dice/cards. It just matters if you got them at all. If you have two values, you can arrange them two ways. Three values you can arrange six ways. Four values you can arrange 20 ways. 0-20 takes a little over four bits to represent. If you have a set, you don’t care about order. So if you save the data without an order to it, it takes a little less space to hold it. About four bits worth. With five values you can save almost seven bits (120) and with six it’s over 9 bits (720).
- huftis 9y agoThis reminds me of the following old puzzle. Ten people are standing in a line. Each person is wearing a black or a white hat and can only see the colours of the hats of the people in front of them. The goal is to guess the colour of one’s own hat. First, the last person in the line shouts out their guess (‘black’ or ‘white’), then the person in front of them shouts out their guess, etc. No other form of communication is allowed (no clapping, no touching, no texting – and no tricks involving, e.g., encoding information in the delay between it being ‘your turn’ and actually shouting out your guess). The group ‘wins’ if at most one person guesses wrong. The group is allowed to discuss a strategy before taking part in this puzzle (i.e., before being given their hats). Which strategy should they choose to maximise the chance of winning? They’re only allowed one wrong guess, so this is basically trying to encode 9 bits of information in 1 bit. And here the ordering of the bits actually matters. Still, it’s possible to choose a strategy which gives the group 100% chance of winning! Good luck trying to solve this one. :)
- steve_musk 9y agoSeems impossible to me.
- Robin_Message 9y agoTry doing it with just two people. Then extend the concept somehow. All the details of the puzzle are important.
- steve_musk 9y agoWell 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.
- Too 9y agoYou 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.
- AlphaGeekZulu 9y agoAhh, just yesterday in HN: Operation Gunman http://www.cryptomuseum.com/covert/bugs/selectric/index.htm 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"?
- YesThatTom2 9y agoWhich reminds of of this old programming joke: While developing a CAD system we saved a lot of RAM compared to our competitor's product. They were storing each (X1,Y1)(X2,Y2) as four integers. We figured out how to the same thing in just 16-bits. Yes, you guessed it (wait for it....) we could fit a edge in word-wise! (Disclaimer: I didn't say it was a GOOD joke!)
- XtremAlRaven 9y agoAny reason why store last 4 bits as is and not just making a LUT out of 4 sorted 5-bit values?
- espeed 9y agoDe Brujin Sequences