Boston, Pearson Education, Inc., 2003
$39.99 US (hardcover)
Hacker's Delight is a treasure trove for learning how to write efficient code. Over the course of 16 chapters and two appendices, fiendishly clever algorithms are illustrated through numerous examples coded in C and with graphics, along with the mathematical theory that supports the techniques.
The introduction describes an instruction set and execution efficiency model on which the rest of the work is based. This provides a useful means for assessing computational efficiency on most modern computers. Then the stage is set for a chapter about many little issues surrounding bit-level representation. Next, a chapter each is provided for algorithms involving power-of-two boundaries and arithmetic bounds.
Efficient techniques for bit-level manipulations, such as counting the bits in a word, are described in the next three chapters, and the next four chapters form an étude about some key arithmetic operators and functions, including efficient multiplication and two kinds of integer division. A chapter follows covering algorithms for computing key elementary functions on integers. This includes logarithms, exponentials, plus square and cube roots.
In some specialized applications, alternative representations for the meaning of the bits can offer an advantage. Unusual number system bases and Gray codes are described in detail in two chapters. Gray codes, for instance, are useful for enumerating states in finite-state machines where only one bit changes per state transition.
One chapter provides an algorithmic glimpse on a variant of the Peano curve called the Hilbert curve, which is an interesting related space-filling curve. The Hilbert curve is amenable to recursive algorithms and has some bit-level computational advantages for representing spatial distances in coordinates. These algorithms find usefulness in image processing, rendering and compression.
A nice summary of IEEE Std 754-1985 floating-point arithmetic includes a procedure for comparing floating-point numbers using only integer operations, formulas for computing the probability density function for the number of leading digits in select ranges of representable numbers and a handy table of miscellaneous number values represented in hex for both single- and double-precision floating point.
The last chapter provides algorithms for computing prime numbers, using Willan's and Wormell's Formulas. Primes have uses in hashing algorithms and cryptography, among other things.
Two appendices provide 4-bit arithmetic tables and a more detailed description of Newton's Method for function approximation. The arithmetic tables are a handy way to envision the work done in algorithmic steps that are a fraction of a typical word length. The bibliography also is rich, listing many original papers for arithmetic, number theory and the techniques embellished within the book.
You can employ these techniques to attain mastery of some important inner-loop code, while enjoying the beauty of arithmetic algorithms. The author is a veteran of IBM, and his programming tricks are born of experience across four decades, from the IBM 704 through the PowerPC. The book is a wonderful collection of techniques for any programmer looking to improve efficiency for key algorithms in areas such as compiler development, databases, arithmetic for image and signal processing, and code libraries.
Free DevOps eBooks, Videos, and more!
Regardless of where you are in your DevOps process, Linux Journal can help!
We offer here the DEFINITIVE DevOps for Dummies, a mobile Application Development Primer, and advice & help from the expert sources like:
- Linux Journal
- New Products
- Users, Permissions and Multitenant Sites
- Flexible Access Control with Squid Proxy
- Security in Three Ds: Detect, Decide and Deny
- High-Availability Storage with HA-LVM
- Tighten Up SSH
- DevOps: Everything You Need to Know
- Solving ODEs on Linux
- Non-Linux FOSS: MenuMeters
- diff -u: What's New in Kernel Development