[Translation] I received a check for $ 0.00 from Knut

[Translation] I received a check for $ 0.00 from Knut


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, or politically incorrect” is considered an error. I really wanted to get a check from Knut, so I decided to look for mistakes in his outstanding work The Art of Programming (TAOCP). I managed to find three. True to the word, Whip sent a check for 0x $ 3.00 .



As you can see, this is not a real check. Previously, Knut sent real checks, but stopped in 2008 due to rampant fraud . He is now sending out “personal certificates of deposit” in San Surriff Bank (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 order of decreasing triviality.

Typo # 1


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

Of course, this error is not surprising. Only in this article there are surely 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 maths section, this is the very first page of the sixth chapter in the “Search”! Perhaps one of the most readable sections of the book. In theory, there should be the least typos, but no.

By the way, if you ever thought of reading TAOCP, try it. Many will say that this is a directory , 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 reach mathematics that you do not understand, skip it and open the next section that you can understand. Reading in this way, I miss at least 80% of the book, but the remaining 20% ​​are great!

It is also said that TAOCP is 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 perform the following steps in a loop:

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

Now consider: how many border checks does this algorithm require, on average? In the worst case, when an array does not contain an element, one check is required for each element in the list, and on average it will be something like $ N/2 $ . 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 perform the following steps in the loop:

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

One way or another, the element is guaranteed to be found, and the border check is performed only once, when this happens. This is a deep idea, but it is simple enough even for a novice programmer. Probably, I can not talk about the relevance of work for others, but I immediately managed to apply this wisdom both in personal and in professional code. The TAOCP book is full of such gems (to be fair, there are many and strange things, such as bubble sort ) .

"Search, search
So long
Search, search
I just wanted to dance "

- Luther Vandross, “Search” (1980)

Typo # 2


The second typo is in Volume 4A, “Combinatorial Algorithms”, part 1. On page 60, the task of scheduling comedians in various casinos is described. As an example, there are several real comedians, including Lily Tomlin, Strange El Jankovic and Robin Williams, who was still alive when the book came out. The whip is always , therefore Williams is referred to on page 882 as "Williams, Robin McLorim." But his middle name ends with “n”, not “m”, that is, Mac-Lorin.

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

“The most important event during the McLorin administration was the declaration of war against Spain by the United States in the spring of 1898 ... Unfortunately, the war may have given some government officials the opportunity to practice bribery. McLorin has been accused of various dubious practices, including nepotism and excessive use of pardon authority. In the era of sobriety, critics blamed the governor for drunkenness, which he publicly acknowledged. "

Historical error


Consider the traditional multiplication algorithm from the school curriculum. How much does it require single-bit multiplication operations? Suppose you multiply $ m $ -bit number $ x $ on  $ n $ -bit  $ y $ . First, multiply the first digit $ x $ for each digit $ y $ in turn.Then multiply the second digit $ x $ for each digit $ y $ in turn, and so on, until you have passed all the digits  $ x $ . Thus, traditional multiplication requires $ mn $ primitive multiplications. In particular, multiplying two numbers by $ n $ bits require  $ n ^ 2 $ one-bit multiplications.

This is bad, but you can optimize the process using the method developed by the Soviet mathematician Anatoly Alekseevich Karatsuba. Suppose that $ x $ and $ y $ - two-digit decimal numbers; that is, there are numbers $ a $ , $ b $ ,  $ c $ ,  $ d $ such that  $ x = (ab) _ {10} $ and  $ y = (cd) _ {10} $ (general The development of this algorithm for large numbers requires certain manipulations; although it is not too difficult, but in order not to be mistaken in details, I would rather stick to a simple example). Then $ x = 10a + b $ ,  $ y = 10c + d $ ,  $ xy = (10a + b) (10c + d) $ . Multiplying binaries gives $ xy = 100ac + 10ad + 10bc + bd $ . At the moment, we still have $ n ^ 2 = 4 $ one-bit multiplications:  $ ac $ ,  $ ad $ ,  $ bc $ ,  $ bd $ . Now add and subtract  $ 10ac + 10bc $ . After several permutations that I leave as an exercise for the reader, - just three one-bit multiplications! (There are some constant coefficients, but they can be calculated only by adding and shifting the digits).

Do not ask for proof, but Karatsuba’s algorithm (recursively generalized from the example above) improves the traditional multiplication method with $ O (n ^ 2) $ operations up to . Please note that this is a real improvement of the algorithm, not an optimization for mental calculations. Indeed, the algorithm is not suitable for mental arithmetic, as it requires large overhead costs for recursive operations. In addition, the effect will not manifest itself fully until the numbers become large enough (fortunately, even faster methods came out of the Karatsuba algorithm: in March 2019, an algorithm was published that requires only n log n multiplications; acceleration is applicable only to unimaginably large numbers).

This algorithm is described on page 295 of the second volume, “Calculated Algorithms”. There, Knuth writes: “It is curious that this idea was discovered only in the 1962 year”, when the article describing the Karatsuba algorithm was published. But! In 1995, Karatsuba published an article entitled “Computation Difficulty,” in which he says several things: 1) around 1956, Kolmogorov suggested that multiplication cannot be done in less than $ O (n ^ 2) $ steps; 2) in 1960 year, Karatsuba attended the seminar, where Kolmogorov expounded his n² hypothesis. 3) "Exactly in a week" Karatsuba developed the algorithm "divide and conquer"; 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 error is that instead of 1962 the year should be specified 1960 . That's it.

Analysis


The search for errors did not require much skill.

  1. The first mistake was as trivial 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 the second typo required good luck and hard work, 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 as pathetic as it seems, because Easter eggs are hidden in Knut’s pointers. For example, there are Arabic and Hebrew entries, and both point to page 66. But none of the languages; instead, they mention “languages ​​that are read from right to left”). And my attention caught the second name. Since I usually read Wikipedia, I checked Robin Williams and noticed the discrepancy.
  3. I’d like to say that I did some serious research to find a historical mistake, but I actually just looked at the Wiki page about the Karatsuba algorithm . In the very first lines it says: “The Karatsuba algorithm is an algorithm for fast multiplication. Discovered by Anatoly Karatsuba in 1960 and published in 1962. ” After that, it only remained to add two and two.

In the future, I would like to find a more significant error, especially in the Knut code. I would also like to find a bug in the first volume of "Fundamental Algorithms". Maybe I would find 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 just three characters: one addition s , replacing m with n and 2 on 0 . Priced at $ 2.56, these are pretty lucrative characters; if you were paid that kind of money, an article of 1000 words (on average, four characters) would bring you ten pieces.
  • With three hexadecimal dollars, I, along with 29 other citizens, share 69th place in the list of the richest depositors of the Bank of San Cerriff (as of May 1, 2019).


Other discussions of checks from Knut


  • How to get a check from Knut

    General recommendations for finding errors in Knut's books. Mainly related to technical errors, which I do not have. There is one sentence I took seriously:

    It is better to wait until you collect a set of errors to send. By combining several real, but not very valuable mistakes, you will increase the likelihood that one of them will be regarded as an error or advice. If you send errors one by one, each one can be rejected.

    I didn’t want to send simply foolish typos, but I listened to the advice and sent a letter only when I found a historical mistake that seemed serious enough.
  • Ashutosh Mehra’s Checks

    Ashutosh Mehra is the third most wealthy contributor to San Serriff with a whopping 0x $ 207, f0 in BoSS.
  • Check for some non-functional errors in real TeX code
  • Miscellaneous: # 1 # 2 # 3 # 4 # 5 # 6

Source text: [Translation] I received a check for $ 0.00 from Knut