glthr.com, by Guillaume Lethuillier

Discovering Errors in Donald Knuth’s TAOCP

Two Reward Checks from the Bank of San Serriffe

Updated 6 min read

As Donald Knuth published, in February 2025, Volume 4, Fascicle 7 of The Art of Computer Programming (TAOCP), on constraint satisfaction, I would like to provide more information about the errors I discovered in 2019 in other volumes, for which I received two Knuth reward checks. To date, my account balance on his “bank”, the Bank of San Serriffe, is still 0x2.40 (hexadecimal dollars): 0x2.00 for two errors, and 0x0.40 for two “valuable suggestions.”

His response to my error reports was faster than I expected: I emailed him four times to report different errors from December 18, 2019, to January 1, 2020 (although Knuth does not typically use email, there is an email address reserved for reporting TAOCP errors, which his assistant prints). He updated the errata on January 1 and responded by postal mail on January 9, 2020.

Envelope from Stanford Engineering, with the printed sender Donald E. Knuth, Professor Emeritus of The Art of Computer Programming, postmarked San Francisco, 9 January 2020, and addressed by hand to the author; the postal address is blurred.

The envelope contained my printed emails with his handwritten notes in pencil and two checks (dated December 24, 2019, and January 1, 2020).

Reward check from Donald Knuth, drawn on the Bank of San Serriffe and dated 24 Dec 2019, crediting the author’s account with 1.00 hexadecimal dollar; the memo reads f8a.2.

Second reward check from Donald Knuth, drawn on the Bank of San Serriffe and dated 01 Jan 2020, crediting the author’s account with 1.40 hexadecimal dollars (one and 64/256); the memo reads 4f5.(66,66)241.

Some reward recipients have shared their letters online, here and there; however, I will paraphrase Knuth’s responses instead of reproducing them verbatim, as they are part of private correspondence (this can change in the future—per express authorization, for instance; in that case, I will update this article to share a full scan of the letters). A notable exception is an excerpt of a letter containing generic information and a good anecdote: Knuth wished me a “Joyeux Noël” (French for “Happy Christmas”) because, probably without realizing it, I sent him an email on December 25.

Header of the author’s printed email about TAOCP Vol. 4, Pre-Fascicle 5c (Dancing Links). Highlighted: next to its date, Wed, Dec 25, 2019, Knuth circled the day and wrote “Joyeux Noël” in pencil.

I was familiar with Algorithm X (which I mentioned in a previous article) before reviewing Volume 4 Pre-Fascicle 5c (published as Volume 4, Fascicle 5)—because exact cover problems are fantastic! I did not expect to find fundamental errors, as Algorithm X has probably been one of the sections most thoroughly reviewed by its creator.

At that time, I kept track of Algorithm X’s states manually (I was on a flight without a computer). I maintained a record of the memory state with pen and paper, an experience that allowed me to focus on the essential details and discover small errors and imprecisions that led to minor corrections.

Reported Errors

Local Variables Not Declared

While the local variables of the first algorithmic step, cover(i), are identified as such, the variables of the subsequent steps are not.

Excerpt of TAOCP defining cover(i) for Algorithm X, formula (12). Highlighted on its first line: “(Here p, l, and r are local variables.)”

Excerpt of TAOCP defining hide(p), formula (13). The variables q, u and d are highlighted where they are first set: nothing says that they are local.

Though this is not particularly problematic (this is trivially inferable from the context), Knuth recognized that it would have been beneficial to state this characteristic for each step explicitly. However, he decided against breaking up Algorithm X between different pages due to space constraints and, therefore, could not add clarifications for each step; he then appropriately quoted Voltaire: “The secret of being a bore is to tell everything.” Nevertheless, Knuth ultimately found an elegant solution (see below).

Reward: 32¢ (0x20¢)

Unused Memory Fields

When it was time to simulate the impact of the algorithm on the memory state, I was confused by this:

Excerpt of TAOCP with Table 1, the initial contents of memory for Algorithm X. Highlighted: the sentence “Fields marked ‘—’ are unused.” and node 30, the last spacer, whose DLINK field holds a dash.

My interpretation was that a program attempting to access one of these unused fields would fail, as I took them to be in an uninitialized state. And indeed, my pen-and-paper program failed when reaching the hide step for the last spacer. Using the memory dump table as an example, covering one of the last nodes after some iterations leads to setting q to 30 and, therefore, to d ← DLINK(30). If an unused field means an uninitialized memory location, then the algorithm’s execution should prematurely stop as, in this example, DLINK(30) = —. However, Knuth clarified that he did not explicitly state the variable was uninitialized; instead, it must be assumed to be initialized, but its value has no impact on the algorithm.

Reward: 32¢ (0x20¢)

Unused Variables

Finally, N and Z were set during the algorithm initialization step, but I did not need to utilize them when manually tracking the memory state.

Opening of Algorithm X (Exact cover via dancing links) in TAOCP. Highlighted in step X1, Initialize: “Also set N to the number of items, Z to the last spacer address”.

According to Knuth, they were, in fact, used in the exercises, notably exercise 83.

Statement of exercise 83 in TAOCP: extend Algorithm C so that a solution containing the jth option for the first covered primary item p leaves the secondary items that end the earlier options uncovered.

To ensure this was the case, he reviewed it and noticed an error: N should be N₁.

Answer to exercise 83 in TAOCP. Highlighted: the condition that j be greater than N, where N should be N₁.

He graciously rewarded me for helping him discover this error. (I transitively found this error, so to speak.)

Reward: $2.56 (0x$1.00)

Corrections

Corrections arising from my emails, all dated January 1, 2020, can be found in the Errata for Volume 4 Fascicle 5, long-form (available here). Specifically, they are listed on pages 5 and 13 of the downloadable compressed PostScript file.

Errata excerpt with two highlighted entries for page 66, dated 01 Jan 2020: “are unused.” becomes “are unused and can contain anything.”, and “(Here p, l, and r are local variables.)” becomes “(Undeclared variables like p, l, r are local.)”

Errata entry for page 241, line 2 of answer 83, dated 01 Jan 2020 and flagged with a triangle: the comparison of j with N becomes a comparison of j with N₁.

It appears that:

  • Knuth clarified what an “unused” field means by stating that such fields are implicitly but necessarily initialized but “can contain anything”.

  • Instead of listing all local variables, he refers to p, l, r as being part of a non-exhaustive list of local variables (“Undeclared variables like p, l, r are local”).

  • Last, in his answer to exercise 83, he replaced N with N₁.

Small Aside: Using a “HeartBeat-Arrow” as Delimiter

Notice how Knuth uses a bespoke symbol (a “heartbeat-arrow”) to indicate the transition from the error to its correction:

Explanatory entry of the errata (page 666, dated 04 Jul 1776). Highlighted: if the book says ‘n’ where it should have said ‘n + 1’, the change is shown as n, a zigzag arrow pointing right, then n + 1.

This is because, as his corrections are inline/embedded (no table), he needed a symbol that is necessarily not already present in his books; otherwise, it could have been confused with a corrected symbol (typically, a simple right-pointing arrow, →, would have most probably been confused with a corrected material implication, and so forth). I believe this is an illustration of a delimiter, a special marker that cannot use the same symbols or structure as the regular text (in an earlier article, I develop this general idea).

Erroneous Reference to an Obscure Article

Reported Error

When reading the section on Hamiltonian paths in antiquity from Volume 4, pre-fascicle 8a, I stumbled upon the reference to a French article about icosahedral objects inscribed with Greek letters: P. Perdrizet, in Bulletin de l’Institut français du Caire 30 (1930), 1-16. I did not find this article in the journal, but instead located it in Bulletin de l’Institut français d’archéologie orientale.

Acknowledging the error, Knuth took the time to review some articles in this journal and strongly recommended a volume about Egyptian poetry: https://ignca.gov.in/Asi_data/31424.pdf. Although he did not specify an article, I believe he referred to Vikentiev, V. (1935). The metrical scheme of the « Shipwrecked Sailor ». Bulletin de l’Institut français d’archéologie orientale, 35(1), 1–40. It is indeed remarkable for that time (see notably Planche 1, page 18 of the PDF).

Reward: $2.56 (0x$1.00)

Correction

There is no erratum, as it is a pre-fascicle that is directly edited.

Here is, as a substitute, a comparison of a version from November 2019, retrieved with the Wayback Machine, and the current one (March 2025):

November 2019 version of the passage “Hamiltonian paths in antiquity”. Highlighted reference: P. Perdrizet, in Bulletin de l’Institut français du Caire 30 (1930), 1–16.

March 2025 version of the same passage. The highlighted reference now reads: P. Perdrizet, in Bulletin de l’Institut français d’archéologie orientale 30 (1930), 1–16.

Conclusion

This event has left me with an immense sense of respect for Donald Knuth’s dedication to accuracy and attention to detail. It was an honor to contribute to the improvement of his work, even if it was just a small (to be honest: minuscule) part. I look forward to continuing my exploration of the latest published TAOCP volume, and discovering more errors to correct.