Reflections on another year of reading Knuth

Almost a year ago, I posted a semi-review, semi-rumination on the first volume of Donald Knuth's classic computer science set, "The Art of Computer Programming". I enjoyed reading it thoroughly enough that there was no question in my mind at the time that I would go on to read volume 2. Having started volume 2 immediately after finishing volume 1, I finally did complete it earlier this month. Now that I've finished volume 2, there's no doubt in my mind that I'll go on to read volume 3, and anything else written by Knuth that I can get my hands on.

If you're not familiar with the series, it's a very academic (but still surprisingly readable) treatment of many of the fundamentals of computer science. Being written by an academic, for academic purposes, each section is rounded out with a series of exercises that were written to solidify the concepts of the section in your mind. Knuth's exercises are notoriously difficult — most of them require you to re-read sections of the book and if you want to solve most of them, you'll have to have a pencil and paper handy, along with a lot of focused concentration. Just as I did with volume 1, I attempted every single exercise. For some (now unfathomable) reason I had it in my head that volume 2 would be easier going than volume 1, but as I discovered, volume 1 was just the warm-up.

Volume 2 consists of just two chapters (chapters 3 and 4 of the overall work). The first chapter of this book, chapter 3, is all about random number generation. You might not think that the topic of random number generation would be able to fill up even fifty pages, let alone the nearly 200 that Knuth dedicates to it, but you'd be mistaken. He starts off by developing a detailed mathematical theory on what "randomness" really means and then goes on to discuss five different ways to test randomness. It had never occurred to me that randomness is something that you even could test, but Knuth shows you how you can apply sophisticated statistical methods to random number generators to test just how random they are. Chapter 4 discusses what he calls arbitrary-precision arithmetic. This includes a deep, deep discussion of floating-point arithmetic as well as high-precision multiplication and modulus operations. Both of these topics were fascinating for me - I spent a lot of time researching both while I was writing Implementing SSL; random-number generation and high- precision arithmetic are two of the most important topics in cryptography, and crucial to get right. Although I considered myself very well-versed on both topics, Knuth had a lot to teach me. For instance, I stated in my own book, without proof, that the fastest way to exponentiate a number was the "square-and-multiply" method — Knuth admonishes authors who state without proof that this is the fastest way to exponentiate numbers and demonstrates (as only he can) that it actually isn't! If you're curious, I'll refer you to section 4.6.3.

The exercises in this book were, subjectively, harder than those in the first volume. I think that this is in part because volume 1 was meant to be a bit more "introductory" and also because the material is more mathematical. As always, Knuth doesn't waste any time with "easy" questions, but instead challenges you to understand the material on a more fundamental level than just reading over it, however carefully, could ever hope to provide. As I did with volume 1, I made a genuine effort to solve each and every exercise in the book other than the "unsolved computer science research problems" (maybe I'll go back to those some day). One thing that puts a lot of people off of TAOCP is Knuth's use of MIX assembler to generate examples. Although I think those people are missing out on a lot of the nuance of the series by skipping over the MIX assembler parts, they will be happy to note that there's really not too much programming in volume 2; it's almost all mathematical theory. I don't remember there being more than one or two programming exercises in this volume. Most of the exercises were heavy math. He calls for a lot of proofs - in many cases I satisfied myself with working a few examples to convince myself that what he wanted to see proven was actually true, stopping short of trying to produce a publication-worthy rigorous mathematical proof. As I said before, don't judge me until you try it yourself.

I've seen it suggested that this series of books is interesting only from a historical perspective and has been been supplanted by better, more modern, more up-to-date treatments like Sedgewick's or CLRS. I've read CLRS (Cormen, Leiserson, Rivest and Stein's "Introduction to Algorithms") carefully as it was my graduate algorithm's course textbook, and quite a bit of Sedgewick's "Algorithms" (since it was undergraduate algorithm's course textbook), and I don't really see that there's a lot of overlap between these sets of books. Of course, any book on algorithms will discuss sorting algorithms and things like red-black trees, but CLRS is more focused on complex algorithms like Djikstra's algorithm and the max-flow/min-cut algorithm, which would almost be out of place in TAOCP. Neither CLRS nor Sedgewick spend any time discussing how floating-point arithmetic is implemented on a real computer or how to maximize the period of a linear congruential random number generator. TAOCP is a lot lower-level than the more contemporary algorithms books — I'd suggest that any serious developer should read them all.

Add a comment:

Completely off-topic or spam comments will be removed at the discretion of the moderator.

You may preserve formatting (e.g. a code sample) by indenting with four spaces preceding the formatted line(s)

Name: Name is required
Email (will not be displayed publicly):
Comment:
Comment is required
My Book

I'm the author of the book "Implementing SSL/TLS Using Cryptography and PKI". Like the title says, this is a from-the-ground-up examination of the SSL protocol that provides security, integrity and privacy to most application-level internet protocols, most notably HTTP. I include the source code to a complete working SSL implementation, including the most popular cryptographic algorithms (DES, 3DES, RC4, AES, RSA, DSA, Diffie-Hellman, HMAC, MD5, SHA-1, SHA-256, and ECC), and show how they all fit together to provide transport-layer security.

My Picture

Joshua Davies

Past Posts