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.
Win an iPhone 6
Enter to Win
|Geek Hide-away in Guatemala - Stay for Free!||Nov 26, 2015|
|Microsoft and Linux: True Romance or Toxic Love?||Nov 25, 2015|
|Non-Linux FOSS: Install Windows? Yeah, Open Source Can Do That.||Nov 24, 2015|
|Cipher Security: How to harden TLS and SSH||Nov 23, 2015|
|Web Stores Held Hostage||Nov 19, 2015|
|diff -u: What's New in Kernel Development||Nov 17, 2015|
- Microsoft and Linux: True Romance or Toxic Love?
- Cipher Security: How to harden TLS and SSH
- Non-Linux FOSS: Install Windows? Yeah, Open Source Can Do That.
- Web Stores Held Hostage
- Geek Hide-away in Guatemala - Stay for Free!
- Firefox's New Feature for Tighter Security
- PuppetLabs Introduces Application Orchestration
- diff -u: What's New in Kernel Development
- It's a Bird. It's Another Bird!
- IBM LinuxONE Provides New Options for Linux Deployment