Hacker's Delight by Henry S. Warren
ispeters-Re5JQEeQqe8AvxtiuMwx3w at public.gmane.org
Mon Sep 14 22:40:21 UTC 2009
I own a copy of Hacker's Delight. It's awesome. These days it's
mostly trivia, but it's fun to exercise your mind by reading it.
One topic I found interesting was alternate bases for numbering.
Everyone here is used to decimal (base 10), nearly everyone should be
familiar with binary (base 2), octal (base 8), and hexadecimal (base
16). Hacker's Delight introduces base -1, and base i or 2i (I forget
which). Not sure imaginary bases are useful for much, but neat
anyway. Another interesting topic is a function for mapping standard
Cartesian co-ordinates to the Dragon Curve and back again.
Apparently, if you're in the business of writing ray tracers, tracing
pixels along the Dragon Curve is more memory-efficient than just
scanning across the screen because you get better locality of
reference, which leads to better use of the various levels of cache.
As for something useful, there are a few examples of branchless
algorithms for computing various useful functions. Usually the
obivous algorithm involves a branch so the branchless versions are fun
to play with. I was inspired by the thinking and was able to build a
"double-ended array" data structure that can efficiently grow in
length in both directions without any branches in the indexer. I
haven't benchmarked it yet so I don't know if there's a performance
benefit to outweigh the obfuscation, but it was a lot of fun to
discover the technique.
Anyway, I found the book easily worth what I paid.
The Toronto Linux Users Group. Meetings: http://gtalug.org/
TLUG requests: Linux topics, No HTML, wrap text below 80 columns
How to UNSUBSCRIBE: http://gtalug.org/wiki/Mailing_lists
More information about the Legacy