How to Get a Knuth Check


The Art of Computer Programming is the most respected book in computing. It has sold over a million copies. It is difficult and rarely read straight through. The material is most often used as a reference by expert programmers, who consider Knuth's writing the definitive treatment.

Knuth takes pains to ensure the accuracy of his work. He asks his readers to report errors. To motivate reports, he offers a small amount of reward money. This reward money is paid out in checks hand-signed by Knuth. The checks are considered to be "among computing's most prized trophies", and are highly sought after.

How to Get a Check

If you've ever written a program then you know how easy it is to make a mistake. A program's first pass through a compiler can be depressing. The list of warnings and errors generated may run for pages, even if the program is short. Longer programs generate more problems. If we somehow had a logic compiler that could check the thousands of pages that make up The Art of Computer Programming, what kind of output would it produce? It's hard to say, but we do have some evidence. Just the errata we know about runs for hundreds of pages. The imaginary, perfect list of errata must run much longer. The Art of Computer Programming has been closely checked already, but it still contains lots of errors waiting to be found.

It isn't as hard to find an error in Knuth as it is sometimes made out to be. The demands it places on a fact checker are actually quite reasonable. I would guess that the top 25% of programmers, at least, are capable of the work. It is enough to be comfortable following proofs, and even a familiarity with proofs is not required if you know how to carefully step through an algorithm. The material you find in Knuth is frequently similar to the material you find in a textbook on algorithms or discrete mathematics.

An in-depth knowledge of mathematics will help, but it is not required. What is required is dedication. Dedication is the crucial element. We can go over several ways to make the work you do more efficient, but nothing will stand in for doing the work in the first place. You will have to spend time working with the book in a series of focused sessions. You do not have to be able to work through everything. Steady progress on material of any kind is enough. You only have to be able to work through something. If you are dedicated you can easily make up for any deficiencies in your understanding of the material.

Being thorough will help you understand the material completely. Perform as many of the calculations as you can. Reproduce missing details. When there is a program to write, write it. The most reliable method for finding errors is to go through and verify the details. Run the assembler programs to make sure they work. Check that sources are quoted accurately.

It will take more time to be thorough. No one who works through material from The Art of Computer Programming works through it quickly. Ashutosh Mehra, who's found about 500 errors, describes himself as a very slow reader who can spend months on a single section. Ashutosh is a gifted individual, and the reason he reads slowly is because the work demands it. We aren't better than Ashutosh at finding errors, and so we should not expect to be able to work through the book at anything but the slow pace he does.

The slow pace can be unsettling. Finding errors in Knuth is an open-ended problem. You can invest hours and hours and have nothing to show for it. It is a bit like research in that way. Progress will not be cumulative. It won't look like a straight line that intersects with the goal. It will look more like a step function: you've either found something or you haven't. This is different from most of the things we work on. Progress is usually cumulative. This subtle distinction contributes to the perception that it is hard to find errors.

Where to Look

The probability you will earn a check is more a function of your dedication than a function of your math skills. You have to be willing to fail a few times. You can't expect to immediately open the book to an error. Instead, expect the process to take more than a few days of dedicated work. This is challenging material, and, because understanding it takes so long, it can appear disappointingly error-free. If you are going about things the right way, you will both work hard and find nothing. Only after you've worked for a while will you find an error.

Once you are committed to finding an error, start by choosing something to focus on. The best thing to focus on is material that is new and underread. Sections that have received little attention are the best place to find errors. These sections are usually in the new material, although sometimes they are in the old material if they have been passed over for one reason or another.

To know when new material is coming out, pay particular attention to the updates Knuth posts on his website. This is the first place new material is announced. Knuth also goes into specifics about what material he would like to see receive more attention. These tips are especially useful. During the production of Volume 4A he posted a list of exercises no one had written him about. This list made finding bugs very easy.

Knuth is always adding to The Art of Computer Programming. He releases new sections first as short electronic fascicles, then as printed fascicles, and then later as a bundle in a single printed volume. When Knuth announces the availability of electronic fascicles, move to get them before other readers. This will give you a head start. The fascicles are new material that has not been error-checked. So they are a good place to go looking. The next fascicles to be released will be the ones for Volumes 4B, 4C, 4D, and so on (see here). You can maximize the effectiveness of your search by waiting until fascicles are announced on the website.

When you start on new material, don't start at the beginning. The majority of readers will concentrate at the beginning. Bugs near the beginning are more likely to be reported. Since only the first bug report counts, you don't want to produce the same bug report as someone else. Start at a later section. This will reduce the chance you duplicate someone else's work.

It is a good idea in general to check material that is newer. If for some reason you decide to go hunting between the release of fascicles, then the best place to look is in the most recent volume. The current latest volume is Volume 4A. Compare the amount of errata available on 4A to the amount available on newer editions of Volumes 1-3. Volume 4A has a higher error rate. The older volumes are relatively stable. The newer material has more errors.

In addition to selecting new material, you should also try to select material that interests you. The Art of Computer Programming touches on all all kinds of topics in discrete mathematics. If you like any kinds of math at all, then the kinds of math you like are bound to be represented. Picking topics you like will make the work more pleasant.

You can also pick material that is easier, but that is a strategy that can be counterproductive. Easier material lets you cover more material in the same amount of time, but easier material is also more likely to have started out correct, or to have been corrected in the past. You might find that the payoff is worse than you expeted. It is better to work on harder material if you can. There are a few benefits to working on harder material. Harder material focuses your attention on the minor details. It makes you really understand what you are reading. When the material is easy for you your mind will tend to fill in the gaps. This is a bad state of mind to have when error-checking.

Resist the tendency to hop around to the easiest parts. If the material is slightly out of your reach, reach slightly farther, don't give up. When you settle on a section work diligently through it. Make it a point to go through the challenging parts as well as the easy ones. If you flit through many sections, you will miss the errors in each of them. They will run outside the borders of your attention. If you work straight through one section, you will be alert for any errors you do come across.

Handcuff yourself to some section. Closely read the material and work through the exercises at the end. There is no penalty for referring to the solutions, so use the solutions as necessary to help solve the problems. The solutions are also source of errors, so be sure to check them as well. Before you start working consult the latest errata for the material you are working on. You do not want to find an error only to learn it has already been reported.

A section's errata offers insight into the section. A small amount of errata suggests that the material is little read, or that the material is excruciatingly accurate. A larger amount of errata suggests that the area has been picked over, or that it is especially prone to errors. Look through the errata ahead of time. It will inform your decision about which sections to inspect.

When you work, read every line as carefully as possible. Go over every letter with labored precision. Working through at this level of precision is like running a compiler on the text: it will generate a list of complaints. If you are looking at the material with a criticial eye, you will have a list of complaints about it. These complaints may only be 'warnings'. They may deal only with the style of the presentation or the arrangement of a certain argument. Probably, they aren't genuine errors. But they are an important sign. The warnings you generate are an indication that you are working at the required level of focus.

Analysis of Knuth

Knuth has been working on the same books for fifty years. His current projection is that Volume 5 will be finished in 2020. After that he plans to work on Volumes 6 and 7. Knuth has a lot of work ahead of him. He relies on error reports to catch the errors he would otherwise miss.

When you write your error report, remember that every line of text is a line Knuth has previously deemed correct. He wrote it, and checked it, and finally concluded he had removed all the errors. If he was able to spot the error in the text he wouldn't have published it. Any errors that remain are necessarily in his blind spot. Knuth knows he can't catch all the errors. In spite of this awareness, he still suffers from the powerful psychological barrier that what he produced at one point appeared correct to him. When you point an error out to Knuth, you can't hint at what the error is. You have to jar his understanding.

Spell out your discovery. Do not be terse in your derivation of the error. Knuth can't spend as much time reading your report as you spent putting it together. Don't mistakenly believe that by not directly pointing out his error you are being polite. Be direct and be clear.

Knuth receives a lot of mail from people who are wrong. If you haven't proved yourself you could be lumped in this category. Write your letter so that this categorization is impossible. Giving a detailed description will reduce the chances your letter is skimmed or dismissed out of hand.

Like most mathematicians, Knuth has a knack for getting the big ideas correct. He rarely gets the big ideas wrong. For that to happen, Knuth would have to fundamentally misunderstand the concept. It may sound strange, but for some reason such misundertandings are exceedingly rare among mathematicians. Expect Knuth to get the underlying idea correct. It is his retelling that should be suspect. When errors occur, they tend to occur in the implementation.

One cause of implementation errors is the transcription of results from other sources. Knuth sometimes transcribes results directly from existing papers and articles. If you notice this situation pay special attention. Conventions differ wildly from book to book and paper to paper. Style is typically unimportant for the purposes of catching errors. That situation changes in the context of transcription. The translation between styles can introduce fundamental errors. If a result relies on a quirk in a notation that was abandoned, then a style change can introduce an error. An error of omission can occur if the transcription neglects to include information that was introduced earlier in an article.

It can help to understand the different kinds of errors that occur. If you browse the errata list you can get a feel for the kind of errors that commonly happen: The set A is mentioned when clearly A' is intended. The term 'odd' is omitted. Some bound is misstated.

There is another class of errors that is purely related to the TeX format. The Art of Computer Programming is written in TeX. TeX is a distinctive coding language, and it has its own set of common problems and pitfalls. For instance, it is possible to create a matching set of parentheses whose heights are mismatched. Without a familiarity with TeX you might not be sensitive to such errors. Familiarity with the TeX language will help you recognize the language-related issues that result in real errors. If you aren't yet fluent in TeX, working through Knuth's TeXbook can help.

When you believe you've found an error, remember your threshold for what constitutes an actual error (worth $2.56) or a valuable suggestion (worth only $0.32) may differ from Knuth's. He has his own set of guidelines. What you consider a bona fide error he may consider only a suggestion. What you consider a valuable suggestion he may think is nothing at all. It is possible to send in a letter full of presumed errors and receive no reward. If you want to receive credit for an error you must really pin Knuth down. The error must be incontrovertible.

A few things aren't worth anything. Matters of mathematical taste — such as the use of fg or gf to denote function composition — never count as errors. It also seems that collisions in notation are discounted, that is, notation overloaded to mean two different things is considered OK. If you find something egregiously bad, it may qualify, but take this as a general rule.

The solutions in the back are also held to a lower standard. Knuth allows the writing in the answer section to be less formal than the writing in the main body of exposition. Lack of rigor in the solutions is less of a concern. If your error report hinges on a questionable problem with a solution, you may want to find something more substantial.

It is better to wait until you have a collection of errors to send in. Bundling several legitimate but low-grade errors together can increase the chance that one is actually treated as an error or a suggestion. Sending several errors in piecemeal could cause each of them to be dismissed out of hand. Knuth remembers who sends him what. If you send him letters full of baseless claims you may find it harder to claim a reward when the error you report is legitimate.


Knuth is very busy. It can take a long time for him to write back. He has estimated the turnaround time to be six months. In the past, his responses have sometimes been delayed for years. You can help Knuth with his correspondence by being careful what you send.

Always review the latest errata. Working from older printings, or failing to check the errata, can sidetrack you with issues that have already been solved. Up-to-date errata for The Art of Computer Programming can be found at Knuth's website.

If you haven't had formal training (or the equivalent) in discrete mathematics, get your work reviewed by someone who has. A university professor is a good choice. With a polite email you may be able to convince one to spend a few moments checking your work. Even readers with solid backgrounds in mathematics are prone to errors. If you value Knuth's time, have someone double-check your work before you send it in, regardless of how confident you are in its correctness.

Knuth is famous for not using email. In spite of this quirk, emailed bug reports do reach him, in the form of hard copy printouts. Printing emails invariably wrecks the formatting, and to begin with emails are a poor way of expressing math. Write your letter using TeX or LaTeX and send the output as an actual piece of paper. As a courtesy, include a self-addressed, stamped envelope with your letter.

In your error report identify the volume, fascicle, page, and problem where the error occurs. Repeat this information on the envelope of the letter. Knuth and his secretary have a system, and they use this information to prioritize incoming mail. Letters that relate to what Knuth is currently focusing on are read ahead of others.

Addendum: Other Checks

There are lesser known ways to get a Knuth check, each of varying respectability.

Knuth issues checks for reporting bugs in his major software packages, TeX and METAFONT. Finding these bugs is at least as hard and at least as valued as finding errors in The Art of Computer Programming. The reward follows a different scheme: the value of finding a bug doubles every year the prize is unclaimed. Identifying bugs in the TeX family of software is harder than identifying bugs in The Art of Computer Programming.

In the index to The Art of Computer Programming Knuth tries to use full names. Instead of "Knuth, D.E." he lists "Knuth, Donald Ervin". Some names are incomplete. Knuth offers a reward for completing an incomplete name. He refers to this as an "easy" task, but it seems to me that the ones not easily solved via online search will involve full-blown detective work.

Knuth has also written several technical books besides The Art of Computer Programming. You can get a check for finding errors in any of them. Some of the books are substantially less read than The Art of Computer Programming.

Knuth has also written several non-technical books. He does issue checks for corrections to these books.