Footnotes
Foreword
1. Why “HAKMEM”? Short for “hacks memo”; one 36-bit PDP-10 word could hold six 6-bit characters, so a lot of the names PDP-10 hackers worked with were limited to six characters. We were used to glancing at a six-character abbreviated name and instantly decoding the contractions. So naming the memo “HAKMEM” made sense at the time—at least to the hackers.
Preface
1. One such program, written in C, is:
main(){char*p=”main(){char*p=%c%s%c;(void)printf(p,34,p,34,10);}%c”;(void)printf(p,34,p,34,10);}
Chapter 2
1. A variation of this algorithm appears in [H&S] sec. 7.6.7.
2. This is useful to get unsigned comparisons in Java, which lacks unsigned integers.
3. Mathematicians name the operation monus and denote it with 
. The terms positive difference and saturated subtraction are also used.
4. A destructive operation is one that overwrites one or more of its arguments.
5. Horner’s rule simply factors out x. For example, it evaluates the fourth-degree polynomial ax4 + bx3 + cx2 + dx + e as x (x(x(ax + b) + c) + d) + e. For a polynomial of degree n it takes n multiplications and n additions, and it is very suitable for the multiply-add instruction.
6. Logic designers will recognize this as Reed-Muller, a.k.a positive Davio, decomposition. According to Knuth [Knu4, 7.1.1], it was known to I. I. Zhegalkin [Matematicheskii Sbornik 35 (1928), 311–369]. It is sometimes referred to as the Russian decomposition.
7. The entire 335-page work is available at www.gutenberg.org/etext/15114.
Chapter 3
1. pop(x) is the number of 1-bits in x.
Chapter 4
1. In the sense of more compact, less branchy, code; faster-running code may result from checking first for the case of no overflow, assuming the limits are not likely to be large.
Chapter 5
1. A full adder is a circuit with three 1-bit inputs (the bits to be added) and two 1-bit outputs (the sum and carry).
2. The flakiness is due to the way C is used. The methods illustrated would be perfectly acceptable if coded in machine language, or generated by a compiler, for a particular machine.
Chapter 7
1. Actually, the first shift left can be omitted, reducing the instruction count to 126. The quantity mv comes out the same with or without it [Dalton].
2. If big-endian bit numbering is used, compress to the left all bits marked with 0’s, and to the right all bits marked with 1’s.
Chapter 8
1. Reportedly this was known to Gauss.
Chapter 9
1. I may be taken to task for this nomenclature, because there is no universal agreement that “modulus” implies “nonnegative.” Knuth’s “mod” operator [Knu1] is the remainder of floor division, which is negative (or 0) if the divisor is negative. Several programming languages use “mod” for the remainder of truncating division. However, in mathematics, “modulus” is sometimes used for the magnitude of a complex number (nonnegative), and in congruence theory the modulus is generally assumed to be positive.
2. Some do try. IBM’s PL.8 language uses modulus division, and Knuth’s MMIX machine’s division instruction uses floor division [Knu7].
3. One execution of the RS/6000’s compare instruction sets multiple status bits indicating less than, greater than, or equal.
4. Actually, the restoring division algorithm can avoid the restoring step by putting the result of the subtraction in an additional register and writing that register into x only if the result of the subtraction (33 bits) is nonnegative. In some implementations this may require an additional register and possibly more time.
Chapter 12
1. The interested reader might warm up to this challenge.
2. This is the way it was done at Bell Labs back in 1940 on George Stibitz’s Complex Number Calculator [Irvine].
Chapter 14
1. Since renamed the ITU-TSS (International Telecommunications Union—Telecommunications Standards Sector).
Chapter 15
1. A perfect code exists for m = 2k – k – 1, k an integer—that is, m = 1, 4, 11, 26, 57, 120,....
2. It is also called the “binomial coefficient” because 
is the coefficient of the term xr yn – r in the expansion of the binomial (x + y)n.
Chapter 16
1. Recall that a curve is a continuous map from a one-dimensional space to an n-dimensional space.
Chapter 17
1. This is not officially sanctioned C, but with almost all compilers it works.
Chapter 18
1. However, this is the only conjecture of Fermat known to be wrong [Wells].
2. Our apologies for the two uses of π in close proximity, but it’s standard notation and shouldn’t cause any difficulty.
3. This is my terminology, not Willans’s.
4. We have slightly simplified his formula.
Answers To Exercises
1. Base –2 also has this property, but not base –1 + i.
2. These formulas were found by the exhaustive expression search program Aha! (A Hacker’s Assistant).
Appendix B
1. Newton’s method for the special case of the square root function was known to Babylonians about 4,000 years ago.