HAKMEM

HAKMEM
 /hak'mem/, n.

   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.
    

HAKMEM

   <publication> /hak'mem/ 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
   flavour.

   HAKMEM is available from MIT Publications as a {TIFF} file.

   (ftp://ftp.netcom.com/pub/hb/hbaker).

   (1996-01-19)