唐纳德·高德纳 是一位计算机科学家，他非常关心他的书的准确性，因此他建议 一十六美元 ($2,56, 0x$1,00) 对于发现的任何“错误”，其中错误被定义为“技术上、历史上、印刷上或政治上不正确”的任何内容。 我真的很想得到高德纳的支票，所以我决定在他的巨著中寻找错误 《编程的艺术》 （TAOCP）。 我们设法找到了三个。 克努特信守诺言，寄了一张支票 0x$3,00.

如您所见，这不是真正的支票。 Knuth 曾经发送真实支票，但由于以下原因于 2008 年停止： 欺诈猖獗。 他现在将“个人存款证明”发送给 圣塞里夫银行 （老板）。 他说如果有必要的话他愿意寄真钱，但似乎太麻烦了。

我发现了两个错别字和一个历史错误。 我将按照重要性递减的顺序列出它们。

错别字#1

第一个错字出现在《排序与搜索》第三卷第392页，倒数第八行：“在一次不成功的搜索之后，有时（有时）需要在包含以下内容的表中输入一条新记录： K; 执行此操作的方法称为搜索和插入算法。 错误在于 某时 一定是 有时.

当然，出现这样的错误并不奇怪。 光是这篇文章就肯定有一些错别字（找到它们没有奖励）。 真正令人惊讶的是，这么长时间以来，它都没有引起人们的注意。 第392页并不是深藏在数学部分，而是 第一页 第XNUMX章“搜索”！ 可能是本书中阅读最多的部分之一。 理论上，错别字应该是最少的，但事实并非如此。

顺便说一句，如果您曾经考虑过阅读 TAOCP，请尝试一下。 很多人会说这是 目录，不适合直接阅读，但事实并非如此。 作者观点鲜明，风格鲜明。 唯一阻碍可读性的是数学的复杂性。 然而，有一个简单的解决方案：阅读直到遇到你不懂的数学，跳过它，然后转到你能理解的下一部分。 这样读起来，我至少错过了这本书的80%，但另外20%很棒！

也有人说，TAOCP 不相关的，已经过时或不适用于“真正的编程”。 这也不是真的。 例如，介绍后的第一部分着眼于在未排序的数组中查找元素。 最简单的算法是所有程序员都熟悉的。 从数组开头开始指针，然后循环执行以下操作：

1. 检查当前元素是否是所需的元素。 如果是，我们将其退回； 否则
2. 检查指针是否在数组边界之外。 如果是，则返回错误； 否则
3. 放大并继续。

现在考虑：该算法平均需要多少次边界检查？ 在最坏的情况下，数组不包含元素，列表中的每个元素都需要一次检查，平均而言，它会类似于 。 一种更智能的搜索算法只需进行一次边界检查就可以逃脱惩罚。 将所需的元素附加到数组的末尾，然后在数组的开头启动指针并循环执行以下操作：

1. 检查当前元素是否是所需的元素。 如果是这样，如果指针位于数组内，我们将返回响应，否则返回错误。 否则
2. 放大并继续。

无论如何，保证能找到该元素，并且在发生这种情况时仅执行一次边界检查。 这是一个深刻的想法，但即使对于新手程序员来说也很简单。 我可能无法谈论这项工作与其他人的相关性，但我立即能够将这种智慧应用到个人和专业代码中。 TAOCP 书中充满了这样的瑰宝（公平地说，里面也有很多奇怪的东西，比如 冒泡排序).

“搜索，搜索
这么久
搜索，搜索
我只是想跳舞”
——路德·范德罗斯，《搜索》(1980)

错别字#2

第二个拼写错误出现在第 4A 卷“组合算法”第 1 部分中。第 60 页描述了一个涉及安排喜剧演员在各个赌场表演的问题。 书中引用了几位现实生活中的喜剧演员作为例子，包括莉莉·汤姆林、怪异阿尔·扬科维奇和罗宾·威廉姆斯，本书出版时罗宾·威廉姆斯还活着。 Knuth 总是在索引中列出全名，因此 Williams 在第 882 页上列为“Williams, Robin McLorim”。 但他的中间名以“n”结尾，而不是“m”，即麦克劳林。

麦克劳林是他母亲的娘家姓。 她是密西西比州第 34 任州长安塞姆·约瑟夫·麦克劳林的曾孙女。 显然，他的统治并没有给人们留下任何美好的印象。 来自书本 《密西西比州：历史》:

“麦克劳林执政期间最重要的事件是1898年春天美国对西班牙宣战……不幸的是，这场战争可能为一些政府官员提供了进行贿赂的机会。 麦克劳林被指控犯有各种可疑行为，包括裙带关系和过度使用赦免权。 在禁酒运动期间，批评者指责州长是个酒鬼，他也公开承认了这一点。”

历史错误

考虑 传统乘法算法 来自学校课程。 需要多少次个位数乘法？ 假设你乘以 -数字 上 -少量 。 首先乘以第一个数字 对于每个数字 逐个。 然后乘以第二个数字 对于每个数字 一项一项地依此类推，直到读完所有数字 。 因此传统的乘法需要 原始乘法。 特别是，将两个数字乘以 所需军衔 个位数乘法。

这很糟糕，但可以使用苏联数学家阿纳托利·阿列克谢耶维奇·卡拉苏巴 (Anatoly Alekseevich Karatsuba) 开发的方法来优化该过程。 让我们假设 и  - 两位十进制数； 也就是说，有数字 , , , 这样 и （将这个算法推广到更大的数字需要一些操作；虽然这不是太困难，但为了不在细节上犯错误，我最好坚持一个简单的例子）。 然后 , , 。 二项式相乘得出 。 目前我们还有 个位数乘法： , , , 。 现在我们来进行加法和减法 。 经过一些重新安排（我将把这些重新安排留给读者作为练习），事实证明  - 只有三个个位数乘法！ （有一些常数系数，但只能通过数字相加和移位来计算）。

不求证据，但 唐叶算法 （从上面的例子递归推广）改进了传统的乘法方法 之前的操作 。 请注意，这是对算法的真正改进，而不是对心算的优化。 事实上，该算法不适合心算，因为它需要大量的递归操作开销。 此外，只有当数字变得足够大时，效果才会完全显现出来（幸运的是，Karatsuba 的算法已被更快的方法所取代：2019 年 XNUMX 月，发布了一种算法，只需要 日志 n 乘法； 加速度仅适用于难以想象的大数）。

该算法在第 295 卷“半数值算法”的第 XNUMX 页中有描述。 高德纳 (Knuth) 写道：“奇怪的是，这个想法只在 1962 年”，当时发表了一篇描述 Karatsuba 算法的文章。 但！ 1995年，Karatuba发表了一篇论文《计算复杂性》，其中说了几件事：1）1956年左右，柯尔莫哥洛夫提出乘法不能在小于 脚步; 2）在 1960 同年，唐叶参加了科尔莫哥洛夫提出假设 n² 的研讨会。 3）“整整一周”，Karatsuba 开发了“分而治之”算法； 4）1962年柯尔莫哥洛夫撰写并发表了一篇文章 代表唐叶 以及算法的描述。 “我是在这篇文章重新发表后才知道的。”

所以错误是，而不是 1962 必须指定 1960 年。 就这样。

分析

发现错误并不需要特殊的技能。

1. 第一个错误尽可能微不足道，并且位于相对明显的位置（本章的开头）。 任何白痴都会发现它； 原来我就是那个白痴。
2. 找到第二个错别字需要运气和勤奋，但不需要技巧。 “威廉姆斯”的索引位于该卷的倒数第二页，这是本书相当突出的部分。 我只是翻了一下索引（其实并不像听起来那么可悲，因为 Knuth 的索引里藏着复活节彩蛋。例如，有阿拉伯语和希伯来语的条目，都指向第 66 页。但是该页没有提到任何一种语言；相反，它指的是“从右到左阅读的语言”）。 第二个名字引起了我的注意。 由于我通常阅读维基百科，所以我查了一下罗宾·威廉姆斯，发现了一个差异。
3. 我希望我可以说我做了认真的研究来发现历史错误，但实际上我只是看看 关于 Karatsuba 算法的维基百科页面。 第一行说：“Karatsuba 算法是一种快速乘法算法。 由 Anatoly Karatsuba 于 1960 年发现并于 1962 年发表。” 之后剩下的就是加二加二了。

将来我希望找到一个更重要的错误，特别是在 Knuth 的代码中。 我还想在《基本算法》第一卷中找到一个错误。 也许我会找到它，但由于某种原因，当地图书馆只有第 2、3 和 4A 卷。

财务事实：

• 总的来说，我对 TAOCP 的贡献只有三个字：一个补充 s， 替代品 m 上 n и 2 上 0。 这些符号的价格为 2,56 美元，利润非常丰厚； 如果给你这么多钱，一篇1000字（平均四个字）的文章就能赚到十块钱。
• 凭借三块十六进制美元，我和其他 29 名公民一起在圣塞里夫银行最富有的储户名单上并列第 69 位（截至 1 年 2019 月 XNUMX 日）。

关于 Knuth 支票的其他讨论

• 如何从高德纳 (Knuth) 处获得支票

  查找高德纳书中错误的一般建议。 它们大多涉及技术错误，而我没有。 我认真对待了其中的一个建议：

  最好等到收集了一组错误后再提交。 通过组合几个真实但不是很有价值的错误，您可以增加其中一个错误实际上被视为错误或建议的可能性。 如果您一次提交一个错误，则每一个错误都可能会被拒绝。

  我不想只发送无意义的打字错误，但只有当我发现一个看起来足够严重的历史错误时，才听取了建议并发送了这封信。

• 阿舒托什·梅赫拉 (Ashutosh Mehra) 的支票

  Ashutosh Mehra 是圣塞里夫第三富有的投资者，在 BoSS 的净资产高达 0x$207.f0。

• 检查真实 TeX 代码中的一些非功能性错误
• 其他： #1 #2 #3 #4 #5 #6

来源： habr.com