The Impact of Donald Knuth's The Art of Computer Programming
For the first time in its long history, The Art of Computer Programming is being made available in digital formats (MOBI, EPUB, PDF, and in Safari Books Online).
To celebrate this milestone, we asked the leaders in computer science to share their thoughts about The Art of Computer Programming (TAOCP). Read on to discover what they have to say.
Also be sure to read our recent interview with Donald Knuth.
The Art of Computer Programming inspired me very early in my career to become interested in the design and analysis of computer algorithms, a subject that I have found fascinating even to this day.
I purchased my first copy of Volume 1 of TAOCP in 1971, when I was a freshman at Long Beach City College. I was taking courses in “Business Data Processing” and computer programming, but that book was my first exposure to Computer Science. I set my sights high, and eventually transferred to complete my undergraduate study at Stanford University, where the mysterious author wrote such marvelous books. I was lucky enough to take Don’s courses, and eventually to do independent research under him. Four decades later, my most cited paper remains the senior project on “multidimensional binary search trees” that I did under Don’s supervision.
So I started reading TAOCP to learn about the wonderful new field of algorithms. I eventually did my Ph.D. thesis in that area, and taught classes on the topic. I frequently consulted TAOCP to find critical details that were glossed over in other presentations. Sometimes I read the books just for history; where else might a computer scientist learn that the true inventors of binary arithmetic were likely English wine merchants? Before the advent of the World Wide Web, the books were a critical reference for obscure details: many a Ph.D. student taking a General Exam went to the index of TAOCP to determine that George Forsythe’s middle name was Elmer, or that Bob Floyd’s middle name was W (note that there is no period!). And I will even admit that before the advent of late-night cable television, I sometimes read the books for humor alone: “Royalties, use of” in the index of volume 3 reveals how Don funded the magnificent pipe organ in his home. It is hard to go more than a few pages in TAOCP without a serious chuckle.
In the early 1980’s, when my professional interests turned from abstract algorithms to writing efficient programs, I returned to mine the books for some of the best examples of efficient code ever collected. In the early 1970’s, the MIX programs were close to the machines I used at the time. In the third millennium, the MMIX programs capture the spirit of common architectures while avoiding the distracting details of any particular machine.
Peter De Vries expressed a deep feeling of every writer: “I love being a writer. What I can’t stand is the paperwork.” I first learned technical writing in Don’s algorithms class at Stanford, and I have practiced it and taught it often since then. Yet still I get stuck—the words just will not come. When that happens, I return to advice that I first learned in Don’s “Notes on Technical Writing”: “When in doubt, read The Art of Computer Programming for outstanding examples of good style.”
The TAOCP volumes have always held a hallowed place on my bookshelf and, especially, in my imagination. Few books so completely convey an authoritative and definite treatment of a topic. I have always felt that I could completely and dependably rely on algorithms as described in those pages. Other texts leave the door to certainty a little loose, or even sometimes ajar, whereas Knuth invariably double locks it. An especially enjoyable dimension of TAOCP is the history Knuth brings to the presentation of an algorithm. Most other texts present an algorithm as stand-alone accomplishment, as if it had been formulated entirely from whole cloth. However, the historical perspective that TAOCP treats us to shows the algorithm to be the product of a long sequence of refinements to a fundamental idea. This dimension not only clarifies the algorithm itself, it also makes it far easier to explore and recall its essential details.
As such, these four volumes represent for me the incarnation of an ideal: remarkable in their esthetics, accurate and definitive in their information, and uniquely engaging in their embrace of details not touched on by competing treatments.
For me, The Art of Computer Programming is like the holy scripture of computer science. It is a broad, deep, and beautiful work that will never become obsolete. Thank you, Don, for sharing your passion with us!
I keep Don's books close at hand (duplicate copies at home and in the office), and I have treasured them ever since I fell in love with computer science as an undergraduate at Yale. For my first job after college, I had to write a Fortran program to rasterize a database of vectors, which involved a disk sort. I spent many hours immersed in Volume 3 studying algorithms such as replacement selection, and I eventually implemented the "natural selection" variant, because my computing platform had a drum which could be used as a reservoir. My program also involved a multiway disk merge, where my experiments validated Don's analysis that buffers should be allocated proportional to the square root of the file size. I implemented coroutine linkage (Volume 1) to simplify the logic of the multiple phases of the program.
My boss at the time grew concerned as weeks went by during which my code consisted mostly of experiments. Eventually, I wrote the program in about a month, and it outperformed the assembly-language program written for the prior version of the system, the first time in the company that their conversion from assembly-language programming to high-level programming did not result in a performance hit. The code-review committee determined, however, that my coroutine linkage was playing "illegally" with the call stack, and I was forced to perform the painful task of "inverting the logic," but the lesson in abstraction remained.
That experience, inspired by Don's textbooks, convinced me to return to school. I entered the graduate program at Carnegie Mellon, where I obtained my Ph.D. applying algorithms to the problems of VLSI (integrated-circuit) computation. When it came time to write my own textbook on algorithms, the grounding that Don's books gave me, which my own programming had borne out in practice, allowed me to stand on the shoulders of a giant.
I distinctly remember the small used bookstore where I purchased Volume 1. I was devoted to Math at the time. Math was hard, deep, and precise, which I loved. I regarded programming as interesting, but somewhat tedious and not too challenging. Volume 1 changed that perception for me. I discovered that programming could be not only challenging but elegant as well. It was a real science. It made me think. Knuth's books gave me even more. The amazing rigor presented in every page pushed me to do the same in my career. I think this was the best lesson they provided. I miss that rigor today. I hope someone out there is considering extending this series to tackle the new breed of computer science problems with the same rigor. Many of today's problems, such as communication, search, and user interface problems, are more people oriented and therefore harder to define, but the rigor is still needed.
Having the books on my bookshelf gave me a sense of security...that pretty much anything I'd wonder about would be explained there. Today Wikipedia serves some of that purpose. It would have been nice 20 years ago to have had a (more) portable version of Knuth so that I could know, wherever I was, that I could quickly look something up. But 20 years ago there was nothing else, so I'd have to wait until I was back at home to consult the copy in my bedroom bookshelves, or wander the halls at work to find someone who had a copy in their office. I did actually have a 2nd copy that was supposed to be at work, but it was always being "borrowed", so I could never find my own copy at work when I needed it.
My first exposure to Knuth's work was in 1973, when I had landed a summer job at the IBM Philadelphia Scientific Center with the APL group of Kenneth Iverson and Adin Falkoff. The Scientific Center, located at 3401 N. Market Street, had a wonderful mathematics library, and when I expressed some interest in computing some fundamental constants to many decimal places, the staff (probably Don Orth) directed me to Seminumerical Algorithms, Volume 2 of Knuth's magnum opus, The Art of Computer Programming. Reading it was like stepping into a new world.
Knuth revealed that doing a good job at programming was more than just putting together lines of code and timing them. One could actually analyze algorithms, determining their running times with great precision. One could prove mathematically that one algorithm was superior to another, and quantify how much better. And the analysis led to all sorts of amazing mathematics, involving asymptotic expansions, power series, and continued fractions. It fundamentally changed the way I viewed the computer.
Almost every page of Seminumerical Algorithms revealed something interesting. On one page, I learned about the binary gcd algorithm, an improvement on Euclid's algorithm. On another, a method for determining the continued fraction for any algebraic number that did not involve computing the number in decimal first. On another, the continued fraction for e-1/n and tanh z. On another, a faster way to factor integers. Lacking the funds to buy the book, I began to photocopy pages that interested me. After a month or so I had photocopied almost the entire book.
And look! Knuth even offered a reward for readers who found errors in his book! In 1975, as a high school senior, I found an error (a small mistake in a factorization table), and sent it off to Knuth. I can still remember the pride I found when I received a check from him in the mail the next week. I never cashed the check, and still have it as a souvenir. (In my letter, I told him how I found his book so exciting that I photocopied nearly all of it; it didn't occur to me that an author expecting royalties might not find this a welcome sort of praise.) He wrote back, "For this you receive a reward of $1; find more errors and you'll be able to buy vol. 3—or make a Xerox copy of the check and cash it 100 times." Eventually I would accumulate 4 Knuth checks totaling $22.72—all still uncashed.
Later, when I attended university, I began to understand Knuth's wider influence. Almost everywhere I turned, Knuth had been there before. When I was interested in computing Euler's constant to thousands of digits, his 1962 paper showed me one way of doing it. When I got interested in paperfolding sequences, I found that his 1970 paper with Chandler Davis, "Number representations and dragon curves", had already proved everything I had and more. I wrote a program to play the guessing game "Master Mind", but then I found his paper, "The computer as master mind", which showed that my ideas were not optimal. His 1966 paper, "An almost linear recurrence", introduced me to the beauty and complexity of non-linear recurrences (even though, as it turns out, Mahler and de Bruijn had already published stronger results). A little-known 1964 paper in the Fibonacci Quarterly introduced me to some interesting series that eventually led to some of my first published papers. I read his marvelous book Surreal Numbers one weekend, and it eventually turned into a junior paper on the subject.
When I was an undergraduate, I wrote a paper on continued fractions that appeared in the Journal of Number Theory. Knuth read it, and included it as an exercise in Seminumerical Algorithms, page 363. (He assigned it a rating of 40, which means a difficulty equivalent to a "term project".) I was amazed to receive a postcard from him, inquiring about my middle name—Knuth is very thorough (some might say obsessive) about including the full name of each person cited in his index. So at age 21 I was pleased to find myself in the index to volume 2, with my unusual middle name, sandwiched between "Shakespeare, William" and "Shamir, Adi".
It wasn't until I became a professor that I really began to appreciate the depth and breadth of Knuth's influence. His 1965 paper, "On the translation of languages from left to right" almost single-handedly developed the techniques that permit fast compilation of programming languages. The Knuth-Morris-Pratt algorithm was a breakthrough that allows linear time pattern matching, and introduced me to what are now called Sturmian words. His 1976 paper, "Big omicron and big omega and big theta", advocated the now-universal asymptotic notation like big-Theta. And his work on TeX created a system that nearly every mathematician and computer scientist uses to write their papers, exams, and homework assignments.
Of course, Knuth is human, and along the way he made some mistakes. I think his development of MIX, an idealized assembly language, was a waste of time and never had any significant influence. And, since I'm not a Christian, his book 3:16 Bible Texts Illuminated leaves me completely cold. But someone who is so productive and influential is allowed a few wrong turns now and then.
I should also say something about Knuth's personality. He is a very kind and considerate person. This is brought out in his version of Christianity, which is extremely humble—just the opposite of the judgmental fundamentalists and creationists. In 2000, when he visited Waterloo to receive an honorary degree and to deliver the Pascal lectures, he brought a copy of his Selected Papers, autographed it, and left it in my mailbox. It is a gift I will always treasure. He has an offbeat sense of humor, as one can see by examining his earliest publication, from MAD magazine. Yet when you are wrong, he does not hesitate to point it out. I have at least two letters from him pointing out errors or disagreements with my work.
So, happy birthday to Donald Knuth! May he live a long life—long enough to complete The Art of Computer Programming, and savor its completion!
Reposted with permission from http://recursed.blogspot.ca/2008/01/donald-knuth-and-me.html.
It’s really quite simple: if I want to know something about an algorithm, I check Knuth first. (Yeah, officially it’s The Art of Computer Programming, but I and many others just say “Knuth”, in part because that encompasses some of his other books such as The Stanford Graphbase.) If he covers what I want to know, it is covered thoroughly and accurately, with a wealth of citations to the literature. If he doesn’t cover it—well, then I have to take my chances elsewhere. There are other books about algorithms and program analysis, many of them quite good, but no other author is as meticulous as Knuth about getting both the facts and the history right. That’s why I have kept the latest editions of “Knuth” literally within arm’s reach of my office chair for over 40 years.
The first editions of volumes 1, 2, and 3 of TAOCP were invaluable references as we developed the ARPANET packet-switch software and moved into what were the early days of the Internet. Later I bought each update edition as it came out.