HAKMEM (1972) | Hacker News Reader

HAKMEM (1972)

inwap.com

132 pointsCieplak28 comments

Item 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 (spoiler: the solution is described on that page).

It'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/

See also Guy Steele's forward to the book, in which he talks about its relationship to HAKMEM.

http://www.hackersdelight.org/foreword.pdf

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

There 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

try the continuous logarithms now! they are very beautiful and more natural to implement in modern computers

Could you point me to a reference?

this is actually the sole appendix of HAKMEM, (and one of my favorite text files ever)

https://perl.plover.com/classes/cftalk/INFO/gosper.txt

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

yes, of course I meant "continued" (this is a common error by speakers of latin languages since we use the same word for both things)

Yeah, this is Hacker News.

Ten years ago, I implemented Gosper's continued fraction arithmetics in Python: 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

Great, I will definitely have a look at it. Did you implement exp(x) for any continued fraction x?

Yes. The key to that is approximating reals by the second Ostrogradsky series (or, more properly, Ostrogradsky-Sierpiński series): x = ⎣x⎦ + 1/q₁ − 1/q₂ + 1/q₃ - 1/q₄ + ⋯, where the denominators qₖ are greedily chosen as the largest possible. The following formulas are true: exp(1/q) = [1; q−1, 1, 1, 3q−1, 1, 1, 5q-1,…], exp(x + y) = exp(x)exp(y), and exp(x - y) = exp(x)/exp(y). The algorithm keeps two most recent partial sums of the O-S series: sₖ₋₁ and sₖ. As long as the partial quotients of exp(sₖ₋₁) and exp(sₖ) are equal, it emits them; otherwise, it computes the next partial sum sₖ₊₁. Similar formulas work for tan(x).

Interestingly, 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?

Yes, this was proved by F. Carlson in 1921 and it is known as the Pólya–Carlson theorem.

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

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

Item 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

I thought indeed that I was making a "spherical cow" joke. I was actually thinking of this: https://tromp.github.io/java/go/twoxtwo.html, so only 1446 nodes after pruning.

> Programs below this line are considered unfeasible.

http://www.inwap.com/pdp10/hbaker/hakmem/proposed.html#item9...

I'm glad they provided this in 'html' format.

I'm looking, but cannot find some way to view the whole thing as a single HTML page (as it should be), so "wget -m -np" it is ..

A single page version is here: http://hakmem.org/

Ah, that is indeed very nice - thanks!

Is there a modern (latex) version? Reading the math on those pages is an arduous undertaking.

Here: w3.pppl.gov/~hammett/work/2009/AIM-239-ocr.pdf

Thanks a lot!

there is a certain charm in the way the formulas are laid out. A latex version would lose it.

Reply on news.ycombinator.com