Hacker's
Delight

Second Edition (Current)

This site is an adjunct to the book Hacker's Delight (Addison-Wesley, 2003, 2012). 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.

This web page is about the second edition of Hacker's Delight. If you're interested in material about the first edition, click here. Both editions are described on Amazon.com and BarnesAndNoble.com.

Usage permissions and restrictions


Sample sections of Hacker's Delight

Table of Contents.
Foreword by Guy Steele
Chapter 2, Basics.
Errata for the second edition, first printing.
Errata for the second edition, second printing.

The second edition has been translated into Korean and is licensed for a translation into Chinese.


Code for the Algorithms in HD

Click here for a directory to the C code for the algorithms that appear in HD second edition. To download all the code, click here. Download hdcodetxt.zip into a directory of your choice, and unzip it there.

To unzip it in Windows XP, enter the complete file name, "hdcodetxt.zip," click File - Extract All... and select all defaults in the extraction wizard.

To unzip it in Windows 7, enter the complete file name, "hdcodetxt.zip," click "Extract all files" in the resulting window, and in the window that comes up, in the folder name, delete the last component ("hdcodetxt") and click "Extract."

Following one of the above procedures makes a directory named "hdcodetxt," containing about 83 files, plus another 17 in subdirectory "hilbert." If it looks ok you can erase hdcodetxt.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 hdcodetxt.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.


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.


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.


Contributions from Correspondents

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

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.


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.

488084
visitors since 1/24/2008