Donald Knuth  is a computer scientist who cares so much about the correctness of his books that he offers one hex dollar ($ 2.56, 0x $ 1.00) for any “error” found, where everything that is “technically, historically, typographically, is considered an error.” or politically wrong. ” I really wanted to get a check from Knut, so I decided to look for errors in his outstanding work “The Art of Programming” (TAOCP). I managed to find three. True to the 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 rampant fraud . Now he sends out "personal certificates of deposit" in the Bank of San Serriff(BoSS). He says he is ready to send real money if necessary, but it seems to be too troublesome.

I found two typos and one historical mistake. I will list them in decreasing order of triviality.

Typo number 1

The first typo is on page 392 of the third volume “Sorting and Searching”, the eighth line from the bottom: “After an unsuccessful search, sometimes (sometime) it is advisable to enter a new record in the table containing K ; the method that does this is called a search and insert algorithm. The error is that instead of sometime should be sometimes .

Of course, such an error is not surprising. Only in this article there are sure to be a few typos (no rewards for finding them). What is really surprising is that it has not been noticed for so long. Page 392 is not buried deep in the math section, this is the very first pagesixth chapter "Search"! Perhaps one of the most read sections of the book. In theory, there should be the least typos, but no.

By the way, if you ever thought to read TAOCP, give it a try. Many will say that this is a guide not intended for direct reading, but this is not true. The author has a clear point of view and a peculiar style. The only thing that prevents readability is the complexity of mathematics. However, there is a simple solution: read until you get to the math you don’t understand, skip it and open the next section that you can understand. Reading this way, I miss at least 80% of the book, but the remaining 20% ​​are great!

TAOCP is also said to be irrelevant., outdated or otherwise inapplicable to “real programming”. This is also not true. For example, in the first section after the introduction, the search for an element in an unsorted array is considered. The simplest algorithm is familiar to all programmers. Run the pointer at the beginning of the array, then do the following in a loop:

1. Check if the current item is desired. If so, return it; otherwise
   
2. Check if the pointer is outside the array. If so, return an error; otherwise
   
3. Increase the pointer and continue.

Now consider: how many border checks does this algorithm require, on average? In the worst case, when the array does not contain an element, one check will be required for each element in the list, and on average it will be something like$$. A smarter search algorithm can do with just one border check. Attach the desired element to the end of the array, then run the pointer at the beginning of the array and follow these steps in a loop:

1. Check if the current item is desired. If so, we return the answer if the pointer is within the array, or an error if it is not. Otherwise
   
2. Increase the pointer and continue.

One way or another, the element is guaranteed to be found, and border checking is performed only once, when this happened. This is a deep idea, but it is simple enough even for a novice programmer. I probably can’t talk about the relevance of the work for others, but I was immediately able to apply this wisdom in both personal and professional code. The TAOCP book is full of such pearls (in fairness, there are many strange things, such as bubble sorting ).

“Search, Search.
It took so long.
Search, search.
I just wanted to dance.”
- Luther Wandross, “Search” (1980)

Typo number 2

The second typo is in Volume 4A, Combinatorial Algorithms, Part 1. On page 60, we describe the task of planning the performances of comedians in various casinos. Some real comedians are cited as an example, including Lily Tomlin, Strange Al Jankovic, and Robin Williams, who was still alive when the book came out. Whip always gives full names in the index , so Williams is referred to on page 882 as "Williams, Robin McLorim." But his middle name ends with "n", and not with "m", that is, McLoreen.

McLorin is his mother's maiden name. She was the great-granddaughter of Anselm Joseph McLorin, 34th Mississippi Governor. His rule, apparently, was not remembered by anything good. From the book Mississippi: History :

“The most important event during the McLorin administration was the United States declared a war of Spain in the spring of 1898 ... Unfortunately, the war may have enabled some government officials to practice bribery. McLorin has been accused of various dubious practices, including nepotism and excessive use of powers of pardon. In the era of sobriety, critics accused the governor of drunkenness, which he publicly admitted. "

Historical mistake

Consider the traditional multiplication algorithm from the school curriculum. How much does it require one-bit multiplication operations? Suppose you multiply$$-bit number $$ on $$-bit $$. First, multiply the first digit$$ for each digit $$take turns. Then multiply the second digit$$ for each digit $$ take turns and so on until you go through all the numbers $$. Thus, traditional multiplication requires$$primitive multiplications. In particular, the multiplication of two numbers by$$ discharges require $$single bit multiplications.

This is bad, but you can optimize the process using the method developed by the Soviet mathematician Anatoly Alekseevich Karatsuba. Let's pretend that$$ and $$ - double-digit decimal numbers; i.e. there are numbers$$, $$, $$, $$ such that $$ and $$(generalization of this algorithm to large numbers requires certain manipulations; although this is not too difficult, but in order not to be mistaken in the details, I better stick to a simple example). Then$$, $$, $$. Multiplication of binomials gives$$. At the moment, we still$$ single bit multiplication: $$, $$, $$, $$. Now add and subtract$$. After a few permutations, which I will leave as an exercise for the reader, it turns out$$ - only three one-bit multiplications! (There are some constant coefficients, but they can only be calculated by adding and shifting the digits).

Don't ask for proof, but the Karatsuba algorithm (recursively generalized from the above example) improves the traditional method of multiplication with$$ operations before $$. Please note that this is a real improvement in the algorithm, not an optimization for mental calculations. Indeed, the algorithm is not suitable for calculating in the mind, since it requires a large overhead for recursive operations. In addition, the effect will not be fully apparent until the numbers become large enough (fortunately, instead of the Karatsuba algorithm, even faster methods came: in March 2019, an algorithm was published that required only n log n multiplications; acceleration is applicable only to unimaginably large numbers).

This algorithm is described on page 295 of the second volume, Algorithms Derived. There Knuth writes: “It is curious that this idea was discovered only in 1962year ”when an article was published describing the Karatsuba algorithm. But! In 1995, Karatsuba published an article, “Complexity of Computing,” 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 hypothesis n². 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 learned about this article after it was reprinted.”

Thus, the mistake is that 1960 should be indicated instead of 1962 . That's all.

Analysis

Finding mistakes did not require much skill.

1. The first mistake was as banal as possible, and was in a relatively prominent place (the beginning of the chapter). Any idiot would find her; I just turned out to be that idiot.
   
2. Finding a second typo required luck and diligence, but not skill. The index for Williams is on the penultimate page of the volume, a rather prominent part of the book. I was just flipping through the index index (this is not so pathetic as it seems because Easter eggs are hidden in Knuth's indexes. For example, there are entries in Arabic and Hebrew, and both of them point to page 66. But this page does not mention either languages; instead, it refers to “languages ​​that are read from right to left”). And my attention was attracted by the middle name. Since I usually read Wikipedia, I checked Robin Williams and noticed a discrepancy.
   
3. I would like to say that I conducted a serious study to find a historical error, but actually just looked at the Wikipedia page about the Karatsuba algorithm . The very first lines say: “The Karatsuba algorithm is a fast multiplication algorithm. Discovered by Anatoly Karatsuba in 1960 and published in 1962. " After that, it remained only to fold twice 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 there are only volumes 2, 3 and 4A in the local library.

Financial facts:

• In total, my contribution to TAOCP consists of only three characters: one adding s , replacing m with n and 2 with 0 . Priced at $ 2.56, these are pretty 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 pieces.
  
• With three hexadecimal dollars, I, together with 29 other citizens, share 69th place in the list of the richest depositors of the Bank of San Serriff (as of May 1, 2019).

Other discussion of Knut checks

• How to get a check from Knut
  
  General guidelines for finding bugs in Knuth's books. Mostly technical errors that I don’t have. There is one suggestion that I took seriously:
  
  

  It’s better to wait until you collect a set of errors to send. By combining several real, but not very valuable errors, you will increase the likelihood that one of them will really be regarded as an error or advice. If you send errors one at a time, each individually may be rejected.

  
  I didn’t want to send just nonsense typos, but I obeyed the advice and sent a letter only when I found a historical error that seemed serious enough.
  
• Checks Ashutosh Mehra
  
  Ashutosh Mehra is the third wealthiest contributor to San Serriff with a whopping fortune of 0x $ 207, f0 in BoSS.
  
• Check for some non-functional errors in real TeX code
  
• Miscellaneous: # 1 # 2 # 3 # 4 # 5 # 6