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

21–30 of 149 posts

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

#21

Post by torstenvl »

yorwba wrote: post #17
torstenvl wrote: post #9

Earlier quoted context omitted.

GNU 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... Note: I was initially annoyed with parent's "do this and see what happens" post and its…

I 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.

There 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.

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

#23

Post by bringtheaction »

LukeShu wrote: post #19
torstenvl wrote: post #9

Earlier quoted context omitted.

GNU 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... Note: I was initially annoyed with parent's "do this and see what happens" post and its…

Your response of linking the GNU Make manual comes of as even more self-impressed and coy than the parent. The parent suggests removing the makefile entirely and running `make main`, and observing the result. That would be a learning experience (and much better than your "RTFM")! But, if you don't want to humor that, the thing to say is: The result is that it works, and correctly builds the program, without a makefil…

> The parent suggests removing the makefile entirely and running `make main`, and observing the result. That would be a learning experience! But, if you don't want to humor that, the thing to say is: The result is that it works, and correctly builds the program, without a makefile at all.

Exactly my intention. Thank you, I was worried after the first response from the other person that I'd worded myself too poorly and that more people would think I was being "self-impressed and coy" when that was not the intention at all.

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

#24

Post by londons_explore »

raphlinus wrote: post #3

This 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.

If I only have 8 bytes of ram and a program counter I can do it...

For (I=0; IShoddy runtime, but hey...

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

#25

Post by yorwba »

torstenvl wrote: post #21
yorwba wrote: post #17

Earlier quoted context omitted.

I 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.

There 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.

From the HN Guidelines:

When disagreeing, please reply to the argument instead of calling names. "That is idiotic; 1 + 1 is 2, not 3" can be shortened to "1 + 1 is 2, not 3."

You may think that encouraging experimentation without giving an explanation is rude, but to me it's just a different way of sharing knowledge.

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

#26

Post by jack9 »

londons_explore wrote: post #18
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.

Your 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...

The maximum entropy is what is important, to the encoding challenge, as I understood it.

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

#27

Post by SilasX »

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 cameldrv said, information theory. The late David MacKay has a good free book:

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.

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

#28

Post by Franciscouzo »

raphlinus wrote: post #3

This 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.

Sure, just pick a sorting algorithm that uses constant memory and the optimal O(n lg n) time complexity:

https://en.wikipedia.org/wiki/Sorting_algorithm#Comparison_o...

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

#29

Post by [deleted] »

jack9 wrote: post #26
londons_explore wrote: post #18

Earlier quoted context omitted.

Your 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...

The maximum entropy is what is important, to the encoding challenge, as I understood it.

[deleted]

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

#30

Post by Merad »

bringtheaction wrote: post #5

That 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.

Heh, that big ass makefile is the generic makefile [1] I came up with a few years ago. Definitely a bit of overkill for a single file project, but some of us are lazy when it comes to such things.

[1]: https://github.com/mbcrawfo/GenericMakefile

Post reply on HN