I received a check from Knut for $ 0x 3.00
Donald Knuth is a computer scientist who cares so much about the accuracy 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 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, 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 . Now he is sending out “personal certificates of deposit” in the Bank of San Serriff (BoSS). He says that he is ready to send real money if necessary, but it seems that this is too troublesome.
I found two typos and one historical mistake. I will list them in order of decreasing triviality.
')
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 error is that instead sometime 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 section with mathematics, this is the very first page of the sixth chapter of 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 reference book , 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:
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 is 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 perform the following steps in a loop:
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 ).
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. Whip always lists full names in the index , so Williams is mentioned on page 882 as "Williams, Robin Mac-Lorim." But his middle name ends with “n”, and 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 "Mississippi: history" :
Consider the traditional multiplication algorithm from the school curriculum. How much does it require single-bit multiplication operations? Suppose you multiply -bit number on -bit . First multiply the first digit. for every number take turns. Then multiply the second digit. for every number take turns and so on until you get all the numbers . Thus, traditional multiplication requires primitive multiplications. In particular, the multiplication of two numbers by discharges required one-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 - two-digit decimal numbers; that is, there are numbers , , , such that and (generalization of this algorithm to large numbers requires certain manipulations; although it is not too difficult, but in order not to be mistaken in details, I would rather follow a simple example). Then , , . Multiplication of binaries gives . At the moment we still have one-bit multiplications: , , , . Now add and subtract . After several 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 be calculated only by addition and shift of digits).
Do not ask for proof, but the Karatsuba algorithm (recursively generalized from the example above) improves the traditional multiplication method with operations up . 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 up instead of the Karatsuba algorithm: in March 2019, an algorithm was published that requires only n log n multiplications; the acceleration is applicable only to unimaginably large numbers).
This algorithm is described on page 295 of the second volume, “Calculated Algorithms”. There, Knut writes: “It is curious that this idea was discovered only in 1962 ,” when an article describing the Karatsuba algorithm was published. But! In 1995, Karatsuba published an article called “The Computation Difficulty,” in which he 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 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 describing the algorithm. "I learned about this article only after it was reprinted."
Thus, the mistake is that 1960 should be indicated instead of 1962 . That's all.
The search for errors did not require special skill.
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:
As you can see, this is not a real check. Previously, Knut sent real checks, but stopped in 2008 due to rampant fraud . Now he is sending out “personal certificates of deposit” in the Bank of San Serriff (BoSS). He says that he is ready to send real money if necessary, but it seems that this is 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 error is that instead sometime 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 section with mathematics, this is the very first page of the sixth chapter of 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 reference book , 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:
- Check if the current item is desired. If so, return it; otherwise
- Check if the pointer is outside the array. If so, return an error; otherwise
- 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 is 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 perform the following steps in a loop:
- Check 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
- Increase the 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, “The Search” (1980)
Typo number 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. Whip always lists full names in the index , so Williams is mentioned on page 882 as "Williams, Robin Mac-Lorim." But his middle name ends with “n”, and 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 "Mississippi: history" :
“The most important event during the McLorin administration was the announcement by the United States of the war of Spain 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 the sobriety movement, critics blamed the governor for drunkenness, which he publicly acknowledged. ”
Historical mistake
Consider the traditional multiplication algorithm from the school curriculum. How much does it require single-bit multiplication operations? Suppose you multiply -bit number on -bit . First multiply the first digit. for every number take turns. Then multiply the second digit. for every number take turns and so on until you get all the numbers . Thus, traditional multiplication requires primitive multiplications. In particular, the multiplication of two numbers by discharges required one-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 - two-digit decimal numbers; that is, there are numbers , , , such that and (generalization of this algorithm to large numbers requires certain manipulations; although it is not too difficult, but in order not to be mistaken in details, I would rather follow a simple example). Then , , . Multiplication of binaries gives . At the moment we still have one-bit multiplications: , , , . Now add and subtract . After several 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 be calculated only by addition and shift of digits).
Do not ask for proof, but the Karatsuba algorithm (recursively generalized from the example above) improves the traditional multiplication method with operations up . 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 up instead of the Karatsuba algorithm: in March 2019, an algorithm was published that requires only n log n multiplications; the acceleration is applicable only to unimaginably large numbers).
This algorithm is described on page 295 of the second volume, “Calculated Algorithms”. There, Knut writes: “It is curious that this idea was discovered only in 1962 ,” when an article describing the Karatsuba algorithm was published. But! In 1995, Karatsuba published an article called “The Computation Difficulty,” in which he 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 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 describing the algorithm. "I learned about this article only after it was reprinted."
Thus, the mistake is that 1960 should be indicated instead of 1962 . That's all.
Analysis
The search for errors did not require special skill.
- The first mistake was as trivial as possible, and was in a relatively prominent place (beginning of chapter). Any idiot would find her; I just turned out to be that idiot.
- Finding a second typo required good 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 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.
- I would like to say that I conducted a serious research to find a historical mistake, but in fact I just looked at the Wikipedia page on 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 only three characters: one adding s , replacing m with n and 2 with 0 . Priced at $ 2.56, these are pretty lucrative characters; if you were paid that kind of money, then an article of 1000 words (on average, four characters) would bring you ten.
- With three hexadecimal dollars, I, along with 29 other citizens, share the 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 offer 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 did not want to send simply foolish typos, but I listened to the advice and sent the letter only when I found a historical mistake that seemed serious enough. - Cheku Ashutosh Mehra
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: https://habr.com/ru/post/452812/
All Articles