Hacker's Delight

 in
The book is a wonderful collection of techniques for any programmer looking to improve efficiency for key algorithms.

Book Review: Hacker's Delight by Henry S. Warren, Jr.

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

______________________

White Paper
Linux Management with Red Hat Satellite: Measuring Business Impact and ROI

Linux has become a key foundation for supporting today's rapidly growing IT environments. Linux is being used to deploy business applications and databases, trading on its reputation as a low-cost operating environment. For many IT organizations, Linux is a mainstay for deploying Web servers and has evolved from handling basic file, print, and utility workloads to running mission-critical applications and databases, physically, virtually, and in the cloud. As Linux grows in importance in terms of value to the business, managing Linux environments to high standards of service quality — availability, security, and performance — becomes an essential requirement for business success.

Learn More

Sponsored by Red Hat

White Paper
Private PaaS for the Agile Enterprise

If you already use virtualized infrastructure, you are well on your way to leveraging the power of the cloud. Virtualization offers the promise of limitless resources, but how do you manage that scalability when your DevOps team doesn’t scale? In today’s hypercompetitive markets, fast results can make a difference between leading the pack vs. obsolescence. Organizations need more benefits from cloud computing than just raw resources. They need agility, flexibility, convenience, ROI, and control.

Stackato private Platform-as-a-Service technology from ActiveState extends your private cloud infrastructure by creating a private PaaS to provide on-demand availability, flexibility, control, and ultimately, faster time-to-market for your enterprise.

Learn More

Sponsored by ActiveState