MIT AI Memo 239 (February 1972). A

legendary collection of neat mathematical and programming hacks

contributed by many people at MIT and elsewhere. (The title of the

memo really is "HAKMEM", which is a 6-letterism for `hacks

memo'.) Some of them are very useful techniques, powerful

theorems, or interesting unsolved problems, but most fall into the

category of mathematical and computer trivia. Here is a sampling

of the entries (with authors), slightly paraphrased:

Item 41 (Gene Salamin): There are exactly 23,000 prime numbers less

than 2^(18).

Item 46 (Rich Schroeppel): The most probable suit

distribution in bridge hands is 4-4-3-2, as compared to 4-3-3-3,

which is the most evenly distributed. This is because the

world likes to have unequal numbers: a thermodynamic effect saying

things will not be in the state of lowest energy, but in the state

of lowest disordered energy.

Item 81 (Rich Schroeppel): Count the magic squares of order 5

(that is, all the 5-by-5 arrangements of the numbers from 1 to 25

such that all rows, columns, and diagonals add up to the same

number). There are about 320 million, not counting those that

differ only by rotation and reflection.

Item 154 (Bill Gosper): The myth that any given programming

language is machine independent is easily exploded by computing the

sum of powers of 2. If the result loops with period = 1

with sign +, you are on a sign-magnitude machine. If the

result loops with period = 1 at -1, you are on a

twos-complement machine. If the result loops with period greater

than 1, including the beginning, you are on a ones-complement

machine. If the result loops with period greater than 1, not

including the beginning, your machine isn't binary -- the pattern

should tell you the base. If you run out of memory, you are on a

string or bignum system. If arithmetic overflow is a fatal error,

some fascist pig with a read-only mind is trying to enforce machine

independence. But the very ability to trap overflow is machine

dependent. By this strategy, consider the universe, or, more

precisely, algebra: Let X = the sum of many powers of 2 =

...111111 (base 2). Now add X to itself:

X + X = ...111110. Thus, 2X = X - 1, so

X = -1. Therefore algebra is run on a machine (the

universe) that is two's-complement.

Item 174 (Bill Gosper and Stuart Nelson): 21963283741 is the only

number such that if you represent it on the PDP-10 as both an

integer and a floating-point number, the bit patterns of the two

representations are identical.

Item 176 (Gosper): The "banana phenomenon" was encountered when

processing a character string by taking the last 3 letters typed

out, searching for a random occurrence of that sequence in the

text, taking the letter following that occurrence, typing it out,

and iterating. This ensures that every 4-letter string output

occurs in the original. The program typed BANANANANANANANA.... We

note an ambiguity in the phrase, "the Nth occurrence of." In one

sense, there are five 00's in 0000000000; in another, there are

nine. The editing program TECO finds five. Thus it finds only the

first ANA in BANANA, and is thus obligated to type N next. By

Murphy's Law, there is but one NAN, thus forcing A, and thus a

loop. An option to find overlapped instances would be useful,

although it would require backing up N - 1 characters before

seeking the next N-character string.

Note: This last item refers to a Dissociated Press

implementation. See also banana problem.

HAKMEM also contains some rather more complicated mathematical and

technical items, but these examples show some of its fun

flavor.

An HTML transcription of the entire document is available at

http://www.inwap.com/pdp10/hbaker/hakmem/hakmem.html.

- moby /moh'bee/
[MIT: seems to have been in use among
model railroad fans years ago.

Derived from Melville's "Moby Dick" (some say from `Moby Pickle').... - cycle: 1. n. The basic unit of computation. What every hacker
wants more of (noted hacker Bill Gosper describes himself as a
"cycle junkie").

One can describe an instruction as taking so many `clock cycles'.... - cycle
1. n. The basic unit of computation. What every
hacker wants more of (noted hacker Bill Gosper described himself as
a "cycle junkie").

One can describe an instruction as taking so many `clock cycles'.... - bit-paired keyboard n.,obs.
(alt. `bit-shift
keyboard') A non-standard keyboard layout that seems to have
originated with the Teletype ASR-33 and remained common for several
years on early computer equipment.

The ASR-33 was a mechanical device (see EOU), so the only way to generate the character codes from keystrokes was by some physical linkage.... - bug n.
An unwanted and unintended property of a program or
piece of hardware, esp.

one that causes it to malfunction. Antonym of feature.... - N: /N/ quant. 1. A large and indeterminate number of objec

"There were N bugs in that crock!" Also used in its original sense of a variable name... - magic number n.
[Unix/C; common] 1. In source code

some non-obvious constant whose value is significant to the operation of a program and that is inserted inconspicuously in-line (hardcoded), rather than expanded in by a symbol set by a commented #define.... - quantifiers
In techspeak and jargon, the standard metric
prefixes used in the SI (Systè

me International) conventions for scientific measurement have dual uses.... - DWIM /dwim/
[acronym, `Do What I Mean'] 1. adj. Able
to guess, sometimes even correctly, the result intended when bogus
input was provided.

2. n. obs. The BBNLISP/INTERLISP function that attempted to accomplish this feat by correcting many of the more common errors....