唐纳德·克努斯 （ Donald Knuth）是一位计算机科学家，他非常在意自己书籍的正确性，因此他为发现的任何“错误”提供1进制美元 （2.56 美元，0x 1.00美元），其中“在技术上，历史上，印刷上都被视为错误”。或在政治上是错误的。” 我真的很想得到Knut的支票，所以我决定在他出色的著作“编程的艺术” （TAOCP）中寻找错误。我设法找到三个。忠实地说，Knut发送了一张0x $ 3.00的支票。

如您所见，这不是真正的检查。克努特过去曾寄过真实的支票，但由于猖 in的欺诈行为于2008年停止营业。现在，他在San Serriff银行（BoSS）发出“个人存款证明”。他说，他已经准备好在必要时汇款，但这似乎太麻烦了。

我发现了两个错别字和一个历史错误。我将以琐碎的降序列出它们。

1号错字

第一个错别字在第三卷“排序和搜索”的第392页上，从底部开始的第八行：“不成功的搜索之后，有时（有时）建议在包含K的表中输入新记录；执行此操作的方法称为搜索和插入算法。错误是有时应该代替某个时间。

当然，这样的错误不足为奇。仅在本文中，肯定会有一些错别字（找到它们没有任何回报）。真正令人惊讶的是，它已经很久没有被注意到了。 392页并未深入数学部分，这是“搜索”第六章的第一页 ！也许是本书中阅读最多的部分之一。从理论上讲，错别字应最少，但不要错别字。

顺便说一句，如果您曾经想阅读TAOCP，请尝试一下。许多人会说这不是直接阅读的指南，但事实并非如此。作者观点清晰，风格独特。唯一妨碍可读性的是数学的复杂性。但是，有一个简单的解决方案：请阅读直到您不懂的数学，然后跳过它，然后打开您可以理解的下一部分。通过这种方式阅读，我至少想念这本书的80％，但是剩下的20％太棒了！

他们还说，TAOCP 与 “真实编程” 无关，已过时或不适用。这也不是真的。例如，在介绍之后的第一部分中，将考虑在未排序的数组中搜索元素。所有程序员都熟悉最简单的算法。在数组的开头运行指针，然后循环执行以下操作：

检查是否需要当前项目。如果是这样，将其退回；否则
检查指针是否在数组之外。如果是这样，则返回错误。否则
增加指针并继续。

现在考虑：该算法平均需要多少个边界检查？在最坏的情况下，当数组中不包含元素时，对于列表中的每个元素，都需要进行一次检查，平均而言，它类似于

N / 2

$N / 2$ 。一种更智能的搜索算法可以仅执行一次边界检查。将所需的元素附加到数组的末尾，然后在数组的开头运行指针，然后循环执行以下步骤：

检查是否需要当前项目。如果是这样，如果指针在数组内，则返回答案，否则返回错误。不然
增加指针并继续。

无论如何，保证可以找到该元素，并且在发生这种情况时仅执行一次边界检查。这是一个很深的想法，但是即使对于初学者来说也足够简单。也许我无法谈论这项工作对其他人的重要性，但是我立即能够将这种智慧运用到个人和专业代码中。 TAOCP的书中满是这样的珍珠（公平地说，有很多奇怪的东西，例如气泡分选）。

“搜索，搜索
这么久
搜索，搜索
我只是想跳舞。”
-Luther Wandross，搜索（1980）

错别字2

第二个错字是在第4A卷，组合算法，第1部分中。在第60页上，我们描述了规划喜剧演员在各种娱乐场中的表演的任务。以一些真正的喜剧演员为例，其中包括莉莉·汤姆林（Lily Tomlin），奇特·阿尔·扬科维奇（Strange Al Jankovic）和罗宾·威廉姆斯（Robin Williams），当这本书问世时他们还活着。 Whip总是在索引中给出全名，因此Williams在882页上被称为“ Williams，Robin McLorim”。但是他的中间名以“ n”结尾，而不是以“ m”结尾，即McLoreen。

麦克洛林是他母亲的娘家姓。她是第34届密西西比州州长安塞尔姆·约瑟夫·麦克洛林的曾孙女。显然，他的统治没有被任何美好的事情记住。摘自《密西西比州：历史》一书：

“麦克罗林政府执政期间最重要的事件是美国于1898年春天宣布对西班牙发动战争。不幸的是，战争可能使一些政府官员行贿。 麦克洛林（McLorin）被指控采取各种可疑的作法，包括裙带关系和过度使用赦免权。 在清醒时代，批评家指责州长醉酒，他公开承认。”

历史错误

考虑学校课程中的传统乘法算法 。一比特乘法运算需要多少？假设你乘

m

$m$ 位编号

x

$x$ 在

n

$n$ 位

y

$y$ 。首先，将第一个数字相乘

x

$x$ 每个数字

y

$y$ 轮流。然后乘以第二个数字

x

$x$ 每个数字

y

$y$ 轮流依次类推，直到您遍历所有数字

x

$x$ 。因此，传统乘法需要

百 万

$百万$ 基本乘法。特别是两个数字的乘积

n

$n$ 放电要求

n^{2}

$n ^ 2$ 一位乘法。

这很不好，但是您可以使用苏联数学家Anatoly Alekseevich Karatsuba开发的方法来优化过程。假设

x

$x$ 和

y

$y$ -两位十进制数字；即有数字

一

$一$ ，

b

$b$ ，

c

$c$ ，

d

$d$ 这样

x = （ a b ）_{10}

$x =（ab）_ {10}$ 和

y = （ c d ）_{10}

$y =（cd）_ {10}$ （将此算法泛化为大数需要进行某些操作；尽管这不太困难，但是为了避免在细节上引起误解，我最好坚持一个简单的示例）。然后

x = 10 a + b

$x = 10a + b$ ，

y = 10 c + d

$y = 10c + d$ ，

x y = （ 10 a + b ） （ 10 c + d ）

$xy =（10a + b）（10c + d）$ 。二项式的乘法给出

x y = 100 a c + 10 a d + 10 b c + b d

$xy = 100ac + 10ad + 10bc + bd$ 。此刻，我们仍然

n^{2} = 4

$n ^ 2 = 4$ 一位乘法：

a c

$ac$ ，

a d

$ad$ ，

b c

$bc$ ，

b d

$bd$ 。现在加减

10 a c + 10 b c

$10ac + 10bc$ 。经过几次排列（我将留给读者练习），结果证明

x y = 110 a c + 11 b d + 10 （ a - b ） （ d - c ）

$xy = 110ac + 11bd + 10（a-b）（d-c）$ -只有三个一位数乘法！（有一些常数，但是只能通过对数字进行相加和移位来计算）。

不需要证明，但是Karatsuba算法 （从上面的示例中递归概括）改进了传统的乘法方法，

O （ n^{2} ）

$O（n ^ 2）$ 之前的操作

O （ n^{（ l g 3 ）} ）

$O（n ^ {（lg 3）}）$ 。请注意，这是对算法的真正改进，而不是对心理计算的优化。实际上，该算法不适合在头脑中进行计算，因为它需要大量的递归操作开销。此外，只有当数字足够大时，效果才会完全显现出来（不幸的是，代替了Karatsuba算法，甚至是更快的方法出现了：2019年3月，发布了一种算法，该算法只需要n log n乘法;加速度仅适用于难以想象的大数字）。

该算法在第二卷的第295页“算法推导”中进行了描述。克努斯（Knuth）写道：“奇怪的是，这个想法直到1962年才被发现”，当时发表了一篇描述Karatsuba算法的文章。但是！ 1995年，唐津（Karatsuba）发表了一篇题为“计算的复杂性”的文章，其中说了几件事：1）1956年左右，科尔摩哥罗夫提出乘法不能在少于1的时间内完成。

O （ n^{2} ）

$O（n ^ 2）$ 步骤； 2） 1960年 ，唐津（Karatsuba）参加了一次研讨会，科尔莫哥罗夫（Kolmogorov）提出了他的假设n²。 3）“恰好在一周内”唐津开发了“分而治之”算法； 4）1962年，Kolmogorov 代表Karatsuba撰写并发表了一篇文章，其中介绍了该算法。 “我只有在转载后才发现这篇文章。”

因此，错误是应该标明1960而不是1962 。仅此而已。

分析方法

寻找错误并不需要太多技巧。

第一个错误是尽可能平常的，并且处于相对突出的位置（本章的开头）。任何白痴都会找到她。我原来就是那个白痴。
寻找第二种错字需要运气和勤奋，但不是技巧。《威廉姆斯》的索引在本书的倒数第二页，是本书的重要部分。我只是翻阅了索引索引（它看起来并不那么可悲，因为复活节彩蛋隐藏在Knuth的索引中。例如，阿拉伯语和希伯来语中有一些条目，它们都指向第66页。语言；而是指“从右到左阅读的语言”）。中间名吸引了我的注意力。由于我通常阅读Wikipedia，因此我检查了Robin Williams并发现了差异。
我想说我进行了认真的研究以发现历史错误，但实际上只是看了有关Karatsuba算法的Wikipedia页面。第一行说：“唐津算法是一种用于快速乘法的算法。由阿纳托利唐津（Anatoly Karatsuba）在1960年发现，并于1962年出版。在那之后，它只剩下两次折叠两次。

将来，我想发现一个更大的错误，尤其是在Knuth的代码中。我也想在第一卷《基本算法》中找到一个错误。也许我会找到它的，但是由于某种原因，本地库中只有卷2、3和4A。

财务事实：

总体而言，我对TAOCP的贡献仅包含三个字符：一个添加s ，将m替换为n ，将2替换为0 。这些价格为2.56美元，是非常有利可图的符号。如果您获得该笔钱，那么一篇1000字（平均每个四个字符）的文章将为您带来10件作品。
我与三位十六进制的美元，连同29位其他公民一起，在圣塞里夫特银行最富有的存款人名单中排名第69位（截至2019年5月1日）。

有关Knut检查的其他讨论

如何从Knut获得支票

在Knut的书中查找错误的一般准则。主要是我没有的技术错误。有一个建议我认真对待：

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

我不想发送胡说八道的错别字，但我听从建议并仅在发现历史上似乎很严重的错误时才写信。
阿舒托什·梅赫拉的支票

阿舒托什·梅赫拉（Ashutosh Mehra）是圣塞里夫特（San Serriff）的第三大富翁，拥有0x $ 207的巨大财富，在BoSS中为f0。
检查真实TeX代码中的一些非功能性错误
杂项：＃1 ＃2 ＃3 ＃4 ＃5 ＃6

我收到了来自Knut的0x $ 3.00支票

1号错字

错别字2

历史错误

分析方法

有关Knut检查的其他讨论

More articles: