{"id":34164,"date":"2019-10-31T21:56:44","date_gmt":"2019-10-31T18:56:44","guid":{"rendered":"https:\/\/prohoster.info\/blog\/ya-poluchil-ot-knuta-chek-na-0x-3-00\/"},"modified":"2019-10-31T21:56:44","modified_gmt":"2019-10-31T18:56:44","slug":"ya-poluchil-ot-knuta-chek-na-0x-3-00","status":"publish","type":"post","link":"https:\/\/prohoster.info\/en\/blog\/news\/ya-poluchil-ot-knuta-chek-na-0x-3-00","title":{"rendered":"I received a check from Knuth for 0x$3.00","gt_translate_keys":[{"key":"rendered","format":"text"}]},"content":{"rendered":"

Donald Knuth<\/b>\u00a0\u2014 a scholar in the field of computer science who cares so much about the accuracy of his books that he offers one hexadecimal dollar<\/b> ($2.56, 0x$1.00) for any found \"mistake,\" where a mistake is defined as anything that is \"technically, historically, typographically, or politically incorrect.\" I was eager to receive a check from Knuth, so I decided to look for errors in his outstanding work \"The Art of Computer Programming\"<\/b> (TAOCP). I managed to find three. True to his word, Knuth sent me a check for 0x$3.00<\/b>.<\/p>\n

\"I
\n
\nAs you can see, this is not a real check. Previously, Knuth used to send real checks, but he stopped in 2008 due to rampant fraud<\/a><\/noindex>. Now he sends out \"personal deposit certificates\" from San Serriffe Bank<\/a><\/noindex> (BoSS). He says he is willing to send real money if necessary, but it seems too cumbersome.
\n<\/a><\/noindex>
\nI found two typos and one historical error. I will list them in order of decreasing triviality.<\/p>\n

Typo #1<\/h1>\n

\nThe 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 desirable to enter a new record into the table containing K<\/i>; the method that does this is called the search and insert algorithm. The error is that instead of sometime<\/i><\/b> should be sometimes<\/i><\/b>.<\/p>\n

Of course, there is nothing surprising about such an error. In this article, there are bound to be several typos (no rewards for finding them). What is truly surprising is how long it went unnoticed. Page 392 is not buried deep in a math section; it is the very first page<\/b> of chapter six \"Searching\"! Perhaps one of the most read sections of the book. Ideally, there should be the fewest typos there, but no.<\/p>\n

By the way, if you ever thought about reading TAOCP, give it a try. Many will say it is a reference manual<\/b>, not intended for direct reading, but that is not true. The author has a clear point of view and a distinctive style. The only thing hindering readability is the complexity of the mathematics. However, there is a simple solution: read until you reach the mathematics you do not understand, skip it, and move on to the next section you can grasp. Reading this way, I skip at least 80% of the book, but the remaining 20% is magnificent!<\/p>\n

It is also said that TAOCP is irrelevant<\/b>, outdated or otherwise inapplicable to \"real programming.\" This is also untrue. For example, in the first section after the introduction, the search for an element in an unsorted array is discussed. The simplest algorithm is known to all programmers. Start the pointer at the beginning of the array, then perform the following steps in a loop:<\/p>\n

    \n
  1. Check if the current element is the desired one. If so, return it; otherwise,\n<\/li>\n
  2. Check if the pointer is out of bounds of the array. If so, return an error; otherwise,\n<\/li>\n
  3. Increment the pointer and continue.<\/li>\n<\/ol>\n

    \nNow let\u2019s consider: how many boundary checks does this algorithm require, on average? In the worst case, when the array contains no elements, each element in the list will require one check, resulting in something like \"I. A smarter search algorithm may only need one boundary check. Attach the desired element to the end of the array, then start the pointer at the beginning of the array and perform the following steps in a loop:<\/p>\n

      \n
    1. Check if the current element is the desired one. If so, return the response if the pointer is within the array bounds, or an error if not. Otherwise,\n<\/li>\n
    2. Increment the pointer and continue.<\/li>\n<\/ol>\n

      \nIn any case, the element will be guaranteed to be found, and the boundary check is performed only once when that happens. This is a profound idea, yet it's simple enough even for a novice programmer. I probably can\u2019t speak to the relevance of this work for others, but I was able to apply this wisdom right away in both my personal and professional code. The book TAOCP is full of such gems (to be fair, there are also many odd things, such as bubble sort<\/a><\/noindex>).<\/p>\n

      \"Searching, searching
      \nSo long
      \nSearching, searching
      \nI just wanted to dance\"<\/i>
      \n\u2014 Luther Vandross, \"Searching\" (1980)<\/p><\/blockquote>\n

      <\/p>\n

      Typo #2<\/h1>\n

      \nThe second error is in volume 4A, \"Combinatorial Algorithms\", part 1. On page 60, there is a problem about scheduling comedian performances in various casinos. Several real comedians are mentioned, including Lily Tomlin, Weird Al Yankovic, and Robin Williams, who was still alive when the book was published. Knuth always provides full names in the index, so Williams is mentioned on page 882 as \"Williams, Robin MacLaurin.\" But his middle name ends with an 'n' and not an 'm', meaning MacLaurin.<\/p>\n

      MacLaurin is the maiden name of his mother. She was the great-granddaughter of Anselm Joseph MacLaurin, the 34th governor of Mississippi. His administration does not seem to be remembered for anything good. From the book \"Mississippi: A History\"<\/a><\/noindex>:<\/p>\n

      \"The most significant event during MacLaurin's administration was the United States' declaration of war against Spain in the spring of 1898... Unfortunately, the war may have provided some public officials with the opportunity to practice bribery. MacLaurin was accused of various questionable practices, including nepotism and excessive use of pardoning powers. During the temperance movement, critics accused the governor of drunkenness, which he publicly admitted.\"<\/i><\/p><\/blockquote>\n

      <\/p>\n

      Historical Error<\/h1>\n

      \nConsider traditional multiplication algorithm<\/b> from the school curriculum. How many single-digit multiplication operations does it require? Suppose you are multiplying \"I-digit number \"I to \"I-digit \"I. First, multiply the first digit \"I by each digit \"I in turn. Then multiply the second digit \"I by each digit \"I in turn and so on, until you have gone through all the digits \"I. Thus, traditional multiplication requires \"I primitive multiplications. Specifically, multiplying two numbers by \"I digits requires \"I single-digit multiplications.<\/p>\n

      This is not ideal, but the process can be optimized using a method developed by Soviet mathematician Anatoly Alexeyevich Karatsuba. Suppose that \"I and \"I\u00a0- are two-digit decimal numbers; that is, there exist numbers \"I, \"I, \"I, \"I such that \"I and \"I (generalizing this algorithm to larger digits requires certain manipulations; while this is not too complicated, to avoid mistakes in the details, I would prefer to stick to a simple example). Then \"I, \"I, \"I. Multiplying binomials gives \"I. At this point, we still have \"I single-digit multiplications: \"I, \"I, \"I, \"I. Now let's add and subtract \"IAfter several rearrangements, which I will leave as an exercise for the reader, it results in \"I\u00a0\u2014 only three single-digit multiplications! (There are some constant coefficients, but they can only be computed by addition and bit shifting).<\/p>\n

      Don't ask for proof, but the Karatsuba algorithm<\/b> (recursively generalized from the example above) improves the traditional method of multiplication from \"I operations down to \"I. 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 incurs significant overhead for recursive operations. Moreover, the effect will not materialize fully until the numbers are sufficiently large (fortunately, even faster methods than the Karatsuba algorithm have emerged: in March 2019, an algorithm was published that requires only n log n<\/i><\/a><\/noindex> multiplications; the acceleration only applies to unimaginably large numbers).<\/p>\n

      This algorithm is described on page 295 of the second volume of \"The Art of Computer Programming\". There, Knuth writes: \"Interestingly, this idea was discovered only in 1962<\/b> year\", when a paper describing the Karatsuba algorithm was published. But! In 1995, Karatsuba published a paper titled \"Complexity of Computation\", where he mentions several things: 1) around 1956, Kolmogorov suggested that multiplication cannot be carried out in less than \"I steps; 2) in 1960<\/b> year, Karatsuba attended a seminar where Kolmogorov presented his hypothesis n\u00b2. 3) \"Exactly one week later\" Karatsuba developed the \"divide and conquer\" algorithm; 4) in 1962, Kolmogorov wrote and published a paper on behalf of Karatsuba<\/i> describing the algorithm. \"I only learned about this article after it was reprinted.\"<\/p>\n

      Thus, the mistake lies in the fact that instead of 1962<\/i> the year should have been specified. 1960<\/i> That's all.<\/p>\n

      Analysis<\/h1>\n

      \nFinding errors didn't require particular skill.<\/b><\/p>\n

        \n
      1. The first mistake was as trivial as possible and was located in a relatively obvious place (the beginning of the chapter). Any idiot would have found it; I just happened to be that idiot.\n<\/li>\n
      2. Finding the second typo required luck and diligence, but not skill. The index for \"Williams\" is located on the penultimate page of the volume, a fairly conspicuous part of the book. I was just flipping through the index (it's not as painful as it seems, because there are Easter eggs hidden in Knuth's indexes. For instance, there are entries in Arabic and Hebrew, and both point to page 66. But neither language is mentioned on that page; instead, it talks about \"languages that read right to left\"). And my attention was caught by the second name. As I usually read Wikipedia, I checked Robin Williams and noticed a discrepancy.\n<\/li>\n
      3. I wish I could say that I conducted serious research to find a historical error, but in reality, I just looked at the Wikipedia page on the Karatsuba algorithm.<\/a><\/noindex>In the very first lines, it states: \"The Karatsuba algorithm is a fast multiplication algorithm. Discovered by Anatoly Karatsuba in 1960 and published in 1962.\" After that, it was just a matter of adding two and two.<\/li>\n<\/ol>\n

        \nIn 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 of \"The Art of Computer Programming\". Perhaps I would have, but for some reason, the local library only has volumes 2, 3, and 4A.<\/p>\n

        Financial facts:<\/b><\/p>\n