Hacker's
Delight

First Edition (old)

This site is an adjunct to the book Hacker's Delight (Addison-Wesley, 2003). It may become a forum for discussions about the kind of algorithms that are in that book. There is no mechanism set up yet for discussion threads, but if you send me email (see the bottom of this page) I'll post it if it seems appropriate. Please also send email if you find errors in the book.

There is nothing here about hacking in the sense of breaking into computers.

A second edition was published in October 2012. The first and second editions are described on Amazon.com and BarnesAndNoble.com. This web page is about the first edition.

Usage permissions and restrictions


Sample sections of Hacker's Delight

Table of Contents
Foreword by Guy Steele
Chapter 2, Basics
Errata for the first, second, fourth, and fifth printings
Errata for the third printing (November 2004)
Errata for the sixth and subsequent printings

Explanation: After the first printing, an errata file was started. The publisher did not incorporate this into the second printing. For the third printing, he made all the corrections known up to that point in time. For the fourth and fifth printings, the publisher subcontracted the production work, and accidentally gave the subcontractor the files for the first printing. The sixth printing corrects all the errors known up to when it was printed (November 2006). Therefore, the best copy to obtain is the sixth or later printing, and the second best is the third printing.

Translations of the first edition are available in Russian, Polish, Japanese, Chinese, and Korean.


Code for the Algorithms in HD

Click here for a directory to the C code for the algorithms that appear in HD, plus some new ones. To download all the code, click here. Download HDcode.zip into a directory of your choice, and unzip it there. To unzip it in Windows XP, just enter the complete file name, "HDcode.zip," click File - Extract All... and select all defaults in the extraction wizard. This will make a directory named "HDcode," containing about 56 files, plus another 16 in subdirectory "hilbert," and another 17 in subdirectory "newCode." If it looks ok you can erase HDcode.zip. You might want to rename the files to delete the ".txt" suffix.


A Hacker's Assistant

A superoptimizer is a program that makes a serious attempt at finding optimal code, in the sense of a minimal number of instructions, for a given function. It works by trying all sequences of computational instructions of a given length, simulating each sequence for various inputs, until it finds (stumbles on) a sequence that matches a given user-defined function.

This site includes a relatively simple superoptimizer that's oriented toward RISC computers and is designed to be easy to tailor to a given instruction set. Click here to see the documentation.

To download the superoptimizer itself, including its documentation, click here. Download aha.zip into a directory of your choice, and unzip it there (as explained above for HDcode.zip). You should get about eight files; the important ones are aha.c, abs.h, aha.pdf, make.bat, and Makefile. If it looks ok you can erase aha.zip.


A Gallery of Graphs of Discrete Functions

Some may find interesting these graphs of discrete and mostly computer-oriented functions. Click on "Graphs" below to obtain them as a PDF file.

If you have Mathematica, click on "Source" to obtain the graphs as a Mathematica notebook file. To hold down on the file size, these are stored without any output. To create the graphs, in Mathematica click Kernel - Evaluation - Evaluate Notebook. Then click on the graphs and slide the handles to stretch to a size that suits you. You can change the values of variables n1 through n4 (near the top of the file) to change the range of values used for the independent variables.
GCD graph

  Add, subtract, and multiply in "computer arithmetic."  Graphs  Source
  GCD and other arithmetic functions related to division.  Graphs  Source
  Logical functions (and, or, xor).  Graphs  Source
  Compress (generalized extract), Sheep and Goats, Rotate Left.  Graphs  Source
  Miscellaneous unary functions (Gray code, shuffle bits, etc.)  Graphs  Source


Computing Magic Numbers

Click here for a page that can be used to compute the "magic numbers" and multiplicative inverses modulo 232. These numbers allow you to convert division by constants into multiplications.


More on Division by Constants

Hacker's Delight has 46 pages on division by constants. Almost all of it is on just one method (with signed and unsigned versions). That's probably overkill, but nevertheless this file has still more on division by constants! Two new methods are given. The first reduces division by a constant to a sequence of elementary instructions (just shifts and adds).

Also given are two methods of computing the remainder of division without computing the quotient! The first method applies only to moduli (divisors) of the form 2k ± 1; it is basically the grade school method of casting out nines. (I wonder if they still teach that.) The other method uses a multiplication (typically by a large number), followed by a right shift (typically by a large amount), followed by a table lookup.

The second method of division by a constant is to compute the remainder, subtract it from the dividend, and then use the "exact division" method that's described in Section 10-15. (This is simply a multiply, preceded or followed by a shift if the divisor is even.)


Cyclic Redundancy Check

This file is a write-up on how to compute the Cyclic Redundancy Check checksum: theory, practice, hardware, and software. The CRC-32 protocol is emphasized.


Error Correcting Codes

This file is an introduction to the theory and practice of error correcting codes. It describes the Hamming code, gives a program for computing and decoding a Hamming code, and describes the basic theoretical problem of binary forward error correcting block codes. The program does ECC (aka EDAC) at the SEC-DED (single error correcting, double error detecting) level on 32 information bits.


Montgomery Multiplication

This file describes the theory and practice of Montgomery multiplication. This is a technique for doing "modular multiplication" (that is, given a, b, and m, of computing ab mod m) that improves performance when several multiplications are to be done with the same values of a, b, and m. In particular, it is useful for computing an mod m for fairly large values of n. This calculation is required for the RSA encription algorithm and the Diffie-Hellman key exchange scheme.

C code for Montgomery multiplication with 64-bit data is given in the code section on this web site. This subject would be of interest only to specialists.


Revisions

Click here for a file that contains new algorithms and miscellaneous revisions that will be in the second edition of Hacker's Delight. (Some good stuff here!)


Contributions from Correspondents

You might enjoy taking Marc LeBrun's Computist Quiz. Most problems are just for fun, but some are even practical! Guaranteed to sharpen your skills.

Here is some miscellaneous material that has not been incorporated elsewhere in this web site.


Related Sites

Hacker's Delight, Amazon.com
Hacker's Delight, Barnes & Noble
The Aggregate Magic Algorithms, 26 bit twiddling algorithms from Hank Dietz and others
The Assembly Gems page, tips for the x86 and M680x0, by John Eckerdal
Bit Twiddling Hacks, by Sean Anderson
HAKMEM, the famous memo is now computer readable! thanks to Henry Baker
Matters Computational: Ideas, Algorithms, Source Code, by Jorg Arndt. LOTS of good stuff here. Also available at major book stores.
Plane Filling Curves, Hilbert's and Moore's, by Alexander Bogomolny
Plane Filling Curves: Peano's & Wunderlich's, by Alexander Bogomolny
Programmer's Heaven
Programming Pages of Jasper Neumann, an especially nice section on bit permutations
A Zillion Monkeys, much about programming, particularly about Intel x86 processors, by Paul Hsieh Has a huge list of sites of interest to computer aficionados.
Income tax help in the Monroe CT area


Recent Changes


Send email to user hankw with domain components us, ibm, and com.

22994
visitors since 1/24/2008