6 ms·
HAKMEM (1972)
- vowelless 9y agoIs there a modern (latex) version? Reading the math on those pages is an arduous undertaking.
- vog 9y agoInterestingly, there's not only theorems but also conjectures in this list. Interesting bit: > ITEM 125 (Polya): > CONJECTURE: If a function has a power series with integer coefficients and radius of convergence 1, then either the function is rational or the unit circle is a natural boundary. > Reference: Polya, Mathematics and Plausible Reasoning, volume 2, page 46. Has this conjecture been proved or disproved by now?
- fdej 9y agoYes, this was proved by F. Carlson in 1921 and it is known as the Pólya–Carlson theorem.
- hakmem 9y agoThere are a lot of pearls in this - I would call it lab book. A while ago, I made a slow Clojure implementation of a generalized version of Bill Gospers continued fraction arithmetics from the HAKMEM http://github.com/timrichardt/stern-brocot-tree http://github.com/timrichardt/stern-brocot-tree
- enriquto 9y agotry the continuous logarithms now! they are very beautiful and more natural to implement in modern computers
- hakmem 9y agoCould you point me to a reference?
- enriquto 9y agothis is actually the sole appendix of HAKMEM, (and one of my favorite text files ever) https://perl.plover.com/classes/cftalk/INFO/gosper.txt https://perl.plover.com/classes/cftalk/INFO/gosper.txt
- hakmem 9y agoGuessed it but you wrote "continuous" instead of "continued" :) I was excited about something new ;) And yes, this text is gold. Bill Gosper is the Hunter S. Thompson of science.
- mci 9y agoTen years ago, I implemented Gosper's continued fraction arithmetics in Python: http://sun.aei.polsl.pl/~mciura/software/cf.py http://sun.aei.polsl.pl/~mciura/software/cf.py My module can also compute exp() and log() as well as trigonometric and inverse trigonometric functions. Here are slides from my presentation about it: http://sun.aei.polsl.pl/~mciura/cf.pdf http://sun.aei.polsl.pl/~mciura/cf.pdf
- mietek 9y ago> Programs below this line are considered unfeasible. http://www.inwap.com/pdp10/hbaker/hakmem/proposed.html#item94 http://www.inwap.com/pdp10/hbaker/hakmem/proposed.html#item9...
- brassattax 9y agoI'm glad they provided this in 'html' format.
- SeanLuke 9y agoIt's worth mentioning that many aspects of HAKMEM have found their way into "Hacker's Delight", one of the more impressive CS books ever published IMHO. http://www.hackersdelight.org/ http://www.hackersdelight.org/ See also Guy Steele's forward to the book, in which he talks about its relationship to HAKMEM. http://www.hackersdelight.org/foreword.pdf http://www.hackersdelight.org/foreword.pdf
- cup-of-tea 9y agoI wouldn't call it a computer science book. It's certainly one of the most impressive programming books, though. These days I do most of my program in languages like Lisp and Python and I am a bit sad that I don't get to apply the bit fiddling type hacks found in that book.
- EdwardCoffin 9y agoItem 70, The chess problem "stolen from Chess for Fun, Chess for Blood" by Lasker is problem 66 from that book [1]. The problem as stated in the memo is wrong: the white bishop is on the eighth rank, not the seventh, so it should say Bishop on KB8, not on KB7. The problem in FEN is then: 5B2/6P1/1p6/8/1N6/kP6/2K5/8 w - - 1 1 The version from Lasker's book is much more interesting. It happens that the version from HAKMEM is also a mate-in-3, but kind of a mundane one, relative to Lasker's anyway. [1] Lasker's book is on Google Books, and you can see the relevant page (page 145) https://books.google.ca/books?id=y90UTQeLeeIC&pg=PA145 https://books.google.ca/books?id=y90UTQeLeeIC&pg=PA145 (spoiler: the solution is described on that page).
- conistonwater 9y agoItem 1 (expressing (p/q)! in terms of other (p/q)!) has no general solution still, as far as I know, but can easily be handled empirically for medium-sized n with the PSLQ algorithm. Item 96 ("Solve go") can be made tractable by setting the board size to n=2.
- strangecasts 9y agoItem 96 ("Solve go") can be made tractable by setting the board size to n=2. At first I thought this was an "assume a spherical cow"-style joke, but no, it turns out there are 386 billion possible games you can play on a 2x2 Go board: http://tromp.github.io/go/legal19.html http://tromp.github.io/go/legal19.html
- conistonwater 9y agoI thought indeed that I was making a "spherical cow" joke. I was actually thinking of this: https://tromp.github.io/java/go/twoxtwo.html https://tromp.github.io/java/go/twoxtwo.html, so only 1446 nodes after pruning.
- drallison 9y agoThis is a classic. IMHO, HAKMEM should be required reading for everyone who programs computers. Likewise, everyone should own and read Hank Warren's Hackers Delight. For advanced practitioners, Knuth's Art of Computer Programming (particularly Volume 4) has some similar material. All explore the deep relationship between mathematics and programming.