The Art of Computer Programming, Volume 2 - Knuth

Volume 2 is Seminumerical Algorithms. I found it really rather disappointing.

This is not to say that it's not very, very clever, and an awful lot of work by someone who is clearly brilliant. It is. Whereas volume 1 demonstrated Knuth to be a low-level hacker, volume 2 demonstrates him to be a strong discrete mathematician. What is also clear is that this isn't a series about useful, everyday computer science.

The book is a strange, strange mix of whatever topics take Knuth's fancy, and it always takes an oblique approach. It's like a whole pile of randomly-chosen research papers glued together, which is not helped by the multi-decade nature of the project making it even more eclectic. The two chapters in the book are "Random numbers" and "Arithmetic".

Random numbers is mostly about statistical tests for determining what good pseudorandom numbers look like. There's a little bit on converting from uniform distributions to other distributions, and the tiniest bit on quasirandom, but mostly it's statistical tests. Which would perhaps be more interesting, except that e.g. the diehard test pack does similar stuff, only with code and things. The actual recommended generators are basically linear contruential with carefully chosen parameters, which is so far away from what's state of the art in e.g. Monte Carlo simulation to be... kinda weird. To see the tangential nature of the book, the chapter ends with a digression on trying to generate a workable definition of what a truely random sequence looks like.

The other chapter is "Arithmetic". A brief flick whetted my appetite with the discussion of different bases - base minus 2 being a new and intriguing idea for me. Sadly, despite the ramble about the history of position number systems, that's about as fun as it gets. After a relatively short discussion of how to implement floating-point arithmetic (with a vague nod to IEEE 754), it moves on to a heavy complexity analysis of Euclid's algorithm, and algorithms to deal with polynomials and power series, which mostly seems to be an excuse to investigate obscure ideas, rather than a straightforward approach to those subjects.

It was from this section that one of my favourite parts of the undergrad course "Andvanced Algorithms" was culled from - how to efficient multiplication of really large numbers using an FFT. So, there are gems in here, but they're difficult to extract, and really not the everyday end of the spectrum. If you wanted to play with this kind of thing, you're probably better off reading research papers.

This, I think, is the fundamental issue with this volume. You'd be better off with Cormen et al for basic (and not so basic) algorithms, plus Numerical Recipes for the fundamentals of numerical algorithms, and then fill in the gaps with research papers. A shame, really.

Posted 2014-03-01.