Charles Hbfs
hbfs.wordpress.com · Personal blog · on HN since 2008
Charles Hbfs writes about algorithms, data encoding, bit tricks, dithering, and low-level programming topics.
What HN saysCommenters cite it for specific pieces, such as pairing functions with good locality, the boiling-the-oceans quip, dithering, and fixed-point line drawing.
34HN people shared it
9linked it in comments
32stories submitted
305story points
10 months agolast shared
2008people per year2026
Most-shared posts
- 1Encoding bit packed integers with fractional numbers of bits3 people · 1 points · first shared 2016 · discussion on HN
- 2To boil the oceans3 people · first shared 2022
- 3(Classes of) Algorithms Every Programmer Must Know About2 people · 44 points · first shared 2020 · discussion on HN
- 4Branchless Equivalents of Simple Functions (2008)2 people · 19 points · first shared 2008 · 2 comments on HN
- 5Compact Tree Storage2 people · 8 points · first shared 2009 · discussion on HN
- 6Phase-In Codes (2009)2 people · 4 points · first shared 2021 · discussion on HN
- 7Is Python Slow?2 people · 4 points · first shared 2009 · discussion on HN
- 8Dithering (2013)2 people · 2 points · first shared 2018 · discussion on HN
- 9Run, Python, Run1 people · 84 points · first shared 2011 · 8 comments on HN
- 10Binary Trees are optimal except when they’re not1 people · 75 points · first shared 2021 · 50 comments on HN
- 11Faster than Bresenham's Algorithm? (2009)1 people · 31 points · first shared 2014 · 8 comments on HN
- 12The Speed Of GCD (2013)1 people · 7 points · first shared 2022 · discussion on HN
- 13Python References vs C and C++1 people · 3 points · first shared 2011 · discussion on HN
- 14Evaluating Polynomials1 people · 2 points · first shared 2020 · discussion on HN
- 15How Python manages its memory, and why it goes wrong if you're not careful1 people · 2 points · first shared 2013 · discussion on HN
What HN people wrote when they linked it
kittoes · 2024-07-24
The boustrophedonic version of Rosenberg-Strong function is my favorite because it doesn't have any such jumps and has better locality preserving qualities than most alternatives.
See https://hbfs.wordpress.com/2018/08/07/moeud-deux/.
lloeki · 2022-09-23
> filling out a 64 bit address space looks tough. I struggled to find something of the same magnitude of 2^64 and I got ‘number of iron atoms in an iron filing’
Reminded me of Jeff Bonwick's answer to the following question about his 'boiling the oceans' quip related to ZFS being a "128 bit filesystem":
> 64 bits would have been plenty ... but then you can't talk out of your ass about boiling oceans then, can you?
Sadly his Sun hosted blog was eaten by the migration to Oracle, so thanks to the Internet Archive again:
http://web.archive.org/web/20061111054630/http://blogs.sun.com/bonwick…
That one dives into some of the "handwaving" a bit:
https://hbfs.wordpress.com/2009/02/10/to-boil-the-oceans/
And that one goes into how much energy it would take to merely spin enough disks up:
https://www.reddit.com/r/DataHoarder/comments/71p8x4/reaching_the_limi…
83457 · 2020-07-11
I had one as kid and picked up one a few years ago. Would have been interesting to see what TI could have done in early computer market if they hadn't crippled the machine (intentionally or not) and not fought third party development.
A game that might interest some here is Tunnels of Doom
http://www.ridingthecrest.com/edburns/classic-gaming/tunnels/
https://hbfs.wordpress.com/2008/12/16/tunnels-of-doom/
agumonkey · 2018-02-11
I can't find it right now but there was a lovely article on old ways and new ways to dither.
other articles:
- https://news.ycombinator.com/item?id=11886318
- https://www.cs.princeton.edu/courses/archive/fall00/cs426/lectures/dit…
- https://hbfs.wordpress.com/2013/12/31/dithering/#more-4980
userbinator · 2014-06-22
Great work, it's always nice to see more Asm projects!
"Bare Metal" - does this mean the RPi can run blob-free?
A possible improvement I suggest is to gfx_draw_line in gfx.s - using a fixed-point algorithm could be simpler and faster: http://hbfs.wordpress.com/2009/07/28/faster-than-bresenhams-algorithm/
someplaceguy · 2024-07-25
I found this part of the code quite funny:
# If there are < 5 items, just return the median if len(l) < 5: # In this case, we fall back on the first median function we wrote. # Since we only run this on a list of 5 or fewer items, it doesn't # depend on the length of the input and can be considered constant # time. return nlogn_median(l) Hell, why not just use 2^140 instead of 5 as the cut-off point, then? This way you'd have constant time median finding for all arrays that can be represented in any real-world computer! :) [1]
[1] According to https://hbfs.wordpress.com/2009/02/10/to-boil-the-oceans/
wantoncl · 2022-02-23
There might be a bit of a problem powering it:
https://hbfs.wordpress.com/2009/02/10/to-boil-the-oceans/
goldenkey · 2021-07-01
The author of this post is oblivious to fractional bit encodings. When encoding an array of items, you can always encode the array optimally, only wasting less than 1 bit.
For example, if we had an array of n test scores from 1-100, we only need ceil(n*log2(100)) bits.
The key is that when reading the values, instead of shifting like we would normally to iterate an array, we instead divide by 100. Instead of masking bits, we get the current value by doing mod 100. Its equivalent to shifting/masking for a power of 2, but extends packing to fractional bits. It's quite beautiful.
Take a look at this blog post to understand more about fractional bit representations:
https://hbfs.wordpress.com/2011/11/01/fractional-bits-part-i/
niftich · 2016-06-18
This blog post [1] and its predecessor explaining Huffman Codes [2] was a very helpful guide for me.
[1] https://hbfs.wordpress.com/2011/11/01/fractional-bits-part-i/
[2] https://hbfs.wordpress.com/2011/05/17/huffman-codes/