Hacker's Delight

Boston, Pearson Education, Inc., 2003

ISBN: 0-201-91465-4

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

—Michael Baxter