MIT HAKMAN

神书，我把其中的公式用LaTeX整理了一下.
目前来看，这本书内容也不少，放在blog里不太合适，准备开一本gitbook

MIT 人工智能实验室的 memo

                            MASSACHUSETTS INSTITUTE OF TECHNOLOGY

​                              ARTIFICIAL INTELLIGENCE LABORATORY

AIM 239                                                                       February 1972

HAKMEM

by ：

• M. Beeler [[email protected]]
• R. W. Gosper [[email protected]]
• R. Schroeppel [[email protected]]

This report describes research done at the Artificial Intelligence Laboratory of the Massachusetts Institute of Technology. Support for the Laboratory's artificial intelligence research is provided in part by the Advanced Research Projects Agency of the Department of Defense under Office of Naval Research contract N00014-70-A-0362-0002.

---

Page 1

Compiled with the hope that a record of the random things people do around here can save some duplication of effort -- except for fun.

Here is some little known data which may be of interest to computer hackers. The items and examples are so sketchy that to decipher them may require more sincerity and curiosity than a non-hacker can muster. Doubtless, little of this is new, but nowadays it's hard to tell. So we must be content to give you an insight, or save you some cycles, and to welcome further contributions of items, new or used.

The classification of items into sections is even more illogical than necessary. This is because later elaborations tend to shift perspective on many items, and this elaboration will (hopefully) continue after publication, since this text is retained in "machinable" form. We forgive in advance anyone deterred by this wretched typography.

People referred to are from the A. I. Lab:

Marvin Minsky        [[email protected]]
Bill Gosper          [[email protected]]
Michael Beeler       [[email protected]]
John Roe
Richard Stallman     [[email protected]]
Jerry Freiberg
Rich Schroeppel      [[email protected]]
Michael Speciner     [ms@color_age.com]
Gerald Sussman       [[email protected]]
Joe Cohen
David Waltz
David Silver

Once at the A. I. Lab but now elsewhere:

Jan Kok                  William Henneman
Rici Liknaitzky          George Mitchell
Peter Samson             Stuart Nelson
Roger Banks              Rollo Silver
Mike Paterson            [[email protected]]

at Digital Equipment Corporation:

Jud Leonard              [[email protected]]
Dave Plumer              
Ben Gurley (deceased)
Steve Root

elsewhere at M.I.T.:

Gene Salamin             [[email protected]]
PDP-1 hackers
Eric Jensen              
Frances Yao
Edward Fredkin           

once at M.I.T., but now elsewhere:

Jackson Wright           Steve Brown
Malcolm Rayfield

in France:

Marco Schutzenberger     Henry Cohen

at Computer Corporation of America:

Bill Mann

at BBN:

Robert Clements

---

Page 2

CAVEATS:

Some of this material is very inside -- many readers will have to excuse cryptic references.

The label "PROBLEM" does not always mean exercise; if no solution is given, it means we couldn't solve it. If you solve a problem in here, let us know.

Unless otherwise stated, all computer programs are in PDP-6/10 assembly language.

CONTENTS, HAKMEM 140

P3 - Geometry, Algebra, Calculus

• Item 1 Fractional factorials
• Item 2 N-gon diagonals
• Item 3 Convergence of Newton's square roots
• Item 4 Quartic discriminant
• Item 5 General discriminant
• Item 6 Symmetric functions
• Item 7 Symmetric functions
• Item 8 Cubic solution
• Item 9 Quartic solution
• Item 10 Trigonometric cubic solution
• Item 11 Conformal mappings of N-space

P6 - Recurrence Relations

• Item 12 Fast Fibonacci Transform
• Item 13 Linear Recurrence Relations
• Item 14 Rapid Recurrences
• Item 15 Chebychev polynomials
• Item 16 Tangents and arctangents

P10 - Boolean Algebra

• Item 17 Minimize AND's
• Item 18 Count monotonic Boolean functions
• Item 19 2-NOT's
• Item 20 Venn Diagrams
• Item 21 Cover character raster
• Item 22 Binary masks
• Item 23 Plus and XOR
• Item 24 Venn Diagrams

P12 - Random Numbers

• Item 25 Random number generators
• Item 26 Gaussian distribution
• Item 27 Random unit vectors in N-space

P13 - Number Theory, Primes, Probability

• Item 28 Mersenne 125 is composite
• Item 29 Probability of largest prime factor
• Item 30 Twin Primes
• Item 31 A Ramanujan problem
• Item 32 Distribution of fractions
• Item 33 Russian doll primes
• Item 34 Factorial and integer square root
• Item 35 Arithmetic progressions
• Item 36 Squares with no zero digits
• Item 37 Numbers with each digit
• Item 38 Forward differences
• Item 39 Sequences of digits
• Item 40 Variance of a sum
• Item 41 Number of primes less than 2^18
• Item 42 Probability of PingPong winner
• Item 43 Multinomial coefficients
• Item 44 Recurrences for multinomial coefficients
• Item 45 Locus of steps
• Item 46 Distribution of bridge hands
• Item 47 Fibonacci series mod P
• Item 48 Visibility on 2D lattice
• Item 49 Magic hexagon
• Item 50 No magic cubes of order 4
• Item 51 No magic tesseract of order 5
• Item 52 Relatively prime probability
• Item 53 Lack of common divisors
• Item 54 Probability of even denominators
• Item 55 Gaussian integers
• Item 56 "Length" of a number
• Item 57 Zero digits in powers of two
• Item 58 Sum of cubes
• Item 59 Interesting square
• Item 60 Perfect numbers
• Item 61 Amicable pairs
• Item 62 Amicable pairs
• Item 63 Joys of 239

P25 - Automata Theory

• Item 64 2-counter machines
• Item 65 Complexity of pi(X)
• Item 66 Space-filling curves

P26 - Games

• Item 67 "Poker coins"
• Item 68 Blackout
• Item 69 Dots
• Item 70 Chess problem
• Item 71 Instant Insanity
• Item 72 Window-dice
• Item 73 Sim
• Item 74 Tactix
• Item 75 Peg solitaire
• Item 76 Hi-Q

P30 - Proposed Computer Programs

- Problem 77 Counting polyominos

• Problem 78 Solve minichess
• Problem 79 Solve the tiger puzzle
• Problem 80 Find smallest squared square
• Problem 81 Counting magic squares
• Problem 82 Counting semigroups
• Problem 83 Counting inscribed circles
• Problem 84 Solve pentominos
• Problem 85 Geometric dissections
• Problem 86 Domino coverings
• Problem 87 Analyze giveaway chess
• Problem 88 Analyze escalation chess
• Problem 89 Analyze "4 pawns"
• Problem 90 Solve Scarne's game Teeko
• Problem 91 Solve "five-in-a-row"
• Problem 92 Solve 4x4x4 Tic-Tac-Toe
• Problem 93 Solve checkers
• Problem 94 Solve Hex
• Problem 95 Solve chess
• Problem 96 Solve Go

P36 - Continued Fractions

• Item 97 Sqrt(2), Sqrt(3)
• Item 98 Minimum of factorial function
• Item 99 Partial quotients in arithmetic progression
• Item 100 Product
• Item 101A Continued fraction representation
• Item 101B Continued fraction arithmetic
• Item 101C Rationals in intervals

P45 - Group Theory

• Item 102 Group-like definitions
• Item 103 Hamiltonian paths
• Item 104 Permuting bits on PDP-6/10

P45 - Set Theory

• Item 105 Closure and complement

P46 - Quaternions

• Item 107 Quaternions

P48 - Polyominos, etc.

• Item 108 Counting polyominos
• Item 109 Tessellating the plane
• Item 110 Covering rectangles
• Item 111 Domino covering
• Item 112 Polyiamonds

P51 - Topology

• Item 113
• Item 114
• Item 115

P54 - Series

• Item 116
• Item 117 Gamma
• Item 118 N^N
• Item 119 Pi series
• Item 120 Accelerating series
• Item 121 Bernoulli polynomials
• Item 122 Parity number
• Item 123 Fourier clocks
• Item 124
• Item 125 Radius of convergence

P61 - Flows and Iterated Functions

• Item 126 Flow for Newton's square root
• Item 127 Polynomial functions which commute
• Item 128 Binary/negative binary radix flow
• Item 129 Flow power series
• Item 130 Flow power series
• Item 131 Arithmetic geometric mean
• Item 132 Loop detector
• Item 133 3 N + 1 problem
• Item 134 Numbers to English words flow
• Item 135 The "C" Curve

P67 - Pi

• Item 136 Gaussian integers
• Item 137 Arctangent formulas for pi
• Item 138 Arctangent formulas for pi
• Item 139 Ramanujan formulas for pi
• Item 140 Continued fraction for pi
• Item 141 Pi digits
• Item 142 Pi from fast trig functions
• Item 143 AGM for elliptic integrals, log, and pi
• Item 144 AGM for pi

P72 - Programming Hacks

• Item 145 Display/sound
• Item 146 Munching squares
• Item 147 Munching squares
• Item 148 Munching squares
• Item 149 Circle algorithm
• Item 150 Circle algorithm
• Item 151 Circle algorithm
• Item 152 Circle algorithm
• Item 153 3D solids on 2D display
• Item 154 Twos-complement arithmetic
• Item 155 Subtract right from left
• Item 156 Make AOBJN pointer
• Item 157 Make AOBJN pointer
• Item 158 Recursive SIN/COS
• Item 159 Recursive SIN/COS
• Item 160 Log base 2
• Item 161 Swap two locations
• Item 162 Swap two bits
• Item 163 Exchange two Lisp variables
• Item 164 Max of byte pointers
• Item 165 Byte pointers
• Item 166 Rotate 3 accumulators
• Item 167 Parity, count, reverse bits
• Item 168 PDP-1 sounds
• Item 169 Count ones
• Item 170 Decimal print routines
• Item 171 Division by zero
• Item 172 Two word Lisp CONS
• Item 173 Fix float
• Item 174 Fix point of float function
• Item 175 Next higher

P82 - Programming Algorithms, Heuristics

• Item 176 BANANA Phenomenon
• Item 177 Drawing Curves Incrementally
• Item 178 Evaluating Functions
• Item 179 Searching Character Strings
• Item 180 Finding Corners in Images

P87 - Hardware

• Item 181 Floating Point
• Item 182 Voltage regulators
• Item 183 Current mirrors
• Item 184 One-shot
• Item 185 Oscillators
• Item 186 FM Radio Link
• Item 187 Phone Line XMTR, RCVR
• Item 188 DC Motor Velocity Servo
• Item 189 Optical Coupler
• Item 190 Photocathode Current Oscillator
• Item 191 Deflection Amplifier

Figures

• P19, 20 | 1a, 1b | Binary integers radix i-1, i+1.
• P21 | 2 | Radix i-1 fraction parts (Knuth).
• P31, 32 | 3a, 3b | Squared square, rectangle.
• P34 | 4 | Square, hexagon dissection.
• P50 | 5 | Hexiamond solutions.
• P58, 59 | 6a, 6b | "clock hands" series.
• P62 | 7 | Binary numbers radix -2.
• P66 | 8 | "C" curves.
• P84 | 9 | Incremental curve drawing.