Donald Knuth and Me

To honor Donald Knuth's 70th birthday, I offer this personal reminiscence about Knuth's influence on me and the wider mathematical and computer science community.

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 totalling $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!