Donald Knuth is a computer scientist who cares so much about the correctness of his books that he suggests one hexadecimal dollar ($2,56, 0x$1,00) for any "error" found, where anything that is "technically, historically, typographically, or politically incorrect" is considered an error. I really wanted to get a check from Knuth, so I decided to look for errors in his outstanding work. "The Art of Programming" (TAOCP). Managed to find three. True to his word, Knut sent a check for 0x$3,00.
As you can see, this is not a real check. Knut used to send real checks, but stopped in 2008 due to . Now he sends out "personal deposit certificates" to (BOSS). He says that he is ready to send real money if necessary, but it seems to be too troublesome.
I found two typos and one historical error. I will list them in decreasing order of triviality.
Typo #1
The first typo is on page 392 of the third volume of "Sorting and Search", eighth line from the bottom: "After an unsuccessful search, it is sometimes (sometime) desirable to introduce a new record into the table containing K; the method that does this is called the search and paste algorithm. The error is that instead of sometime should be Sometimes.
Of course, there is nothing surprising in such an error. Only in this article there are sure to be a few typos (no rewards for finding them). What's really amazing is that it's been overlooked for so long. Page 392 isn't buried deep in the math section, it's very first page the sixth chapter "Search"! Possibly one of the most read sections of the book. In theory, there should be the least typos, but no.
By the way, if you've ever thought about reading TAOCP, give it a try. Many will say that this directory, not meant to be read directly, but that's not true. The author has a clear point of view and a peculiar style. The only thing hindering readability is the complexity of the math. However, there is a simple solution: read until you get to the math you don't understand, skip it and go to the next section you can understand. By reading this way, I miss at least 80% of the book, but the other 20% are great!
It is also said that TAOCP irrelevant, is deprecated or otherwise inapplicable to "real programming". This is also not true. For example, the first section after the introduction deals with finding an element in an unsorted array. The simplest algorithm is familiar to all programmers. Start a pointer at the beginning of the array, then do the following in a loop:
- Check if the current element is the desired one. If so, return it; otherwise
- Check if the pointer is outside the array. If so, we return an error; otherwise
- Increase the pointer and continue.
Now consider: how many bounds checks does this algorithm require, on average? In the worst case, when the array contains no element, one check would be required for each element in the list, and on average it would be something like . A smarter search algorithm can get by with just one bounds check. Attach the desired element to the end of the array, then start the pointer at the beginning of the array and do the following in a loop:
- Check if the current element is the desired one. If so, we return a response if the pointer is within the array, or an error if it is not. Otherwise
- Increase the pointer and continue.
Either way, the element is guaranteed to be found, and bounds checking is only done once, when that happens. It's a deep idea, but it's simple enough even for a novice programmer. Probably, I can't speak about the relevance of the work for others, but I immediately managed to apply this wisdom in both personal and professional code. The TAOCP book is full of such gems (to be fair, there are a lot of strange things in there, such as ).
"Search, search
So long
Search, search
I just wanted to dance"
β Luther Vandross, The Search (1980)
Typo #2
The second typo is in Volume 4A, "Combinatorial Algorithms", Part 1. On page 60, the task of scheduling comedian performances in various casinos is described. Several real-life comedians are cited as examples, including Lily Tomlin, Weird Al Yankovic, and Robin Williams, who was still alive when the book came out. Whip always lists full names in the index, which is why Williams is referred to on page 882 as "Williams, Robin McLorim." But his middle name ends in 'n', not 'm', which is McLaurin.
McLaurin is his mother's maiden name. She was the great granddaughter of Anselm Joseph McLaurin, 34th Governor of Mississippi. His reign, apparently, was not remembered for anything good. From book :
βThe most important event during the McLaurin administration was the declaration of war on Spain by the United States in the spring of 1898β¦ Unfortunately, the war may have given some government officials the opportunity to practice bribery. McLaurin was accused of various questionable practices, including nepotism and excessive use of pardon powers. During the era of the temperance movement, critics accused the governor of drunkenness, which he publicly admitted."
historical error
Consider traditional multiplication algorithm from the school curriculum. How many single-bit multiplications does it require? Suppose you multiply -bit number on -bit . Multiply the first number first for every digit in turn. Then multiply the second number for every digit one by one, and so on, until you have passed all the numbers . So traditional multiplication requires primitive multiplications. In particular, multiplying two numbers by discharges requires single digit multiplications.
This is bad, but you can optimize the process using a method developed by the Soviet mathematician Anatoly Alekseevich Karatsuba. Let's pretend that ΠΈ - two-digit decimal numbers; that is, there are numbers , , , such that ΠΈ (Generalizing this algorithm to large numbers requires some manipulation; although this is not too difficult, but in order not to be mistaken in the details, I'd better stick to a simple example). Then , , . The multiplication of binomials gives . At the moment we still have single digit multiplication: , , , . Now add and subtract . After a few permutations, which I will leave as an exercise for the reader, we get β just three single-digit multiplications! (There are some constant coefficients, but they can only be calculated by adding and shifting digits).
Don't ask for proof, but Karatsuba's algorithm (recursively generalized from the example above) improves on the traditional multiplication method with operations up to . Please note that this is a real improvement of the algorithm and not an optimization for mental calculations. Indeed, the algorithm is not suitable for mental counting, as it requires a large overhead for recursive operations. In addition, the effect will not fully manifest itself until the numbers become large enough (fortunately, instead of the Karatsuba algorithm, even faster methods have come: in March 2019, an algorithm was published that requires only multiplications; acceleration only applies to unimaginably large numbers).
This algorithm is described on page 295 of the second volume "Derived Algorithms". There Knut writes: βIt is curious that this idea was discovered only in 1962 yearβ when an article describing the Karatsuba algorithm was published. But! In 1995, Karatsuba published an article "Computation Complexity", which says several things: 1) around 1956, Kolmogorov suggested that multiplication cannot be done in less than steps; 2) in 1960 Karatsuba attended a seminar where Kolmogorov presented his nΒ² conjecture. 3) "Exactly in a week" Karatsuba developed the "divide and conquer" algorithm; 4) in 1962 Kolmogorov wrote and published an article on behalf of Karatsuba with a description of the algorithm. "I only found out about this article after it was reprinted."
So the error is that instead of 1962 must be specified 1960 year. That's all.
Analysis
Finding errors did not require much skill.
- The first mistake was as banal as it gets, and was in a relatively prominent place (beginning of a chapter). Any idiot would have found it; I just happened to be that idiot.
- Finding the second typo required luck and diligence, but not skill. The index for "Williams" is on the penultimate page of the volume, a fairly prominent part of the book. I was just flipping through the index (not as pathetic as it sounds, because there are Easter eggs hidden in Knuth's indexes. For example, there are entries in Arabic and Hebrew, and both point to page 66. But this page does not mention either of languages; instead, it mentions "languages ββthat read from right to left"). And my attention was attracted by the second name. Since I usually read Wikipedia, I checked Robin Williams and noticed an inconsistency.
- I wish I could say that I did some serious research to find a historical error, but really I just looked . In the very first lines it is written: βThe Karatsuba algorithm is a fast multiplication algorithm. Discovered by Anatoly Karatsuba in 1960 and published in 1962. After that, all that was left was to add two and two.
In the future, I would like to find a more significant error, especially in Knuth's code. I would also like to find a bug in the first volume "Fundamental Algorithms". Maybe I would have found it, but for some reason the local library only has volumes 2, 3 and 4A.
Financial Facts:
- In total, my contribution to TAOCP consists of only three characters: one addition s, replacement m on n ΠΈ 2 on 0. Priced at $2,56, these are quite lucrative symbols; if you were paid that kind of money, then an article of 1000 words (on average, four characters each) would bring you ten grand.
- With three hexadecimal dollars, I, along with 29 other citizens, are ranked 69th on the list of the richest savers of the San Serriff Bank (as of May 1, 2019).
Other discussions of Knuth's checks
-
General recommendations for finding errors in Knuth's books. Mostly related to technical errors that I do not have. There is one suggestion that I took seriously:
It's best to wait until you have a set of errors to submit. By combining several real, but not very valuable mistakes, you increase the likelihood that one of them will actually be regarded as a mistake or advice. If you submit bugs one at a time, each one may be rejected individually.
I didn't want to send just silly typos, but took the advice and sent the letter only when I found a historical error that seemed serious enough.
-
Ashutosh Mehra is the third richest contributor to San Serriff with a whopping 0x$207.f0 fortune in BoSS.
- Miscellaneous:
Source: habr.com