HAKMEM

2 definitions found

From Jargon File (4.3.1, 29 Jun 2001) [jargon]:

  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'.
  
  

From The Free On-line Dictionary of Computing (27 SEP 03) [foldoc]:

  HAKMEM
       
           /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)