问题标签 [knuth]

我一直在阅读 Donald Knuth 的《计算机编程艺术》第 1 卷。现在我读完了第一部分，所有的数学都被解释了，非常愉快。不幸的是，在第。121 他开始解释这种MIX基于真实机器语言的虚构机器语言，随后他将解释所有算法，而 Knuth 先生完全失去了我。

我希望这里有人“说”一点，MIX可以帮助我理解它。具体来说，他在开始解释不同的操作并展示示例（第 125 页起）时迷失了我。

Knuth 使用以下形式的“指令格式”：

他还解释了不同字节的含义：

所以正确的字节是要执行的操作（例如，LDA“加载寄存器A”）。F 字节是对具有字段规范 (L:R) 的操作代码的修改，其中 8L + R（例如，C=8 和 F=11 产生“使用 (1:3) 字段加载 A 寄存器）。然后 +/- AA 是地址，I 是修改地址的索引规范。

嗯，这对我来说有点道理。但随后 Knuth 举了一些例子。第一个我确实理解，除了一些位，但我无法理解第二个示例的最后三个，也无法理解下面示例 3 中更困难的操作。

这是第一个例子：

LDA 2000只需加载完整的单词，我们就可以在寄存器 A 中看到它rA。第二个LDA 2000(1:5)加载从第二位（索引 1 ）到末尾（索引 5）的所有内容，这就是加载除加号之外的所有内容的原因。第三个LDA 2000(3:5)只加载从第三个字节到最后一个字节的所有内容。另外LDA 2000(0:3)（第四个例子）有点道理。应该复制 -803 并取 - 并将 80 和 3 放在末尾。

到目前为止一切顺利，在 number5 中，如果我们遵循相同的逻辑，LDA2000(4:4)它只传输第四个字节。它确实做到了最后一个位置。但是，LDA 2000(1:1)只有第一个字节（符号）应该被复制。这很奇怪。为什么第一个值是 + 而不是 - （我希望只复制 - ）。为什么其他值都是0，最后一个问号？

然后他给出了操作的第二个例子STA（存储 A）：

再次，STA 2000和STA 2000(1:5)用STA 2000(5:5)相同的逻辑有意义。然而，Knuth 确实如此STA 2000(2:2)。您可能希望在寄存器 A 中复制等于 7 的第二个字节。但是不知何故，我们最终得到了- 1 0 3 4 5. 我已经看了好几个小时了，不知道这个，或者后面的两个示例（STA 2000(2:3)和STA 2000(0:1)）如何导致显示的位置内容。

我希望这里有人能对这最后三个人大放光彩。

ADD此外，我对他解释操作、、、SUB和MUL的页面也有很大的麻烦DIV。第三个例子，见

这第三个示例是我要理解的最终目标，现在它完全零意义。这非常令人沮丧，因为我确实想继续使用他的算法，但如果我不理解MIX，我将无法理解其余的！

我希望这里有人上过课程MIX或看到了我看不到的东西，并愿意分享他或她的知识和见解！

在 The Art of Computer Programming, Volume 1, Fascicle 1, Knuth (2005) 的第 2 页上写道，“同样的数字也可以通过使用罗马数字以更简单的方式获得。”

这是 Knuth 对 MMIX 计算机识别号的幽默解释的一部分。数字 2009 是其他 14 台计算机的识别号的平均值。他接着说，我们也可以通过“取罗马数字”来获得 2009。如何？

我尝试从其他 14 台计算机的名称中提取罗马数字。总和超过 2009 年，远小于 28,126，所以无论是总和还是平均工作量都不是。Knuth 可能只是意味着采用 MMIX 的罗马数字，如果是这样，那很好。还有别的吗？我愿意知道。

附言

版主，这个问题可能不符合 SO 标准。在这种情况下，请教我在哪里或如何问这个问题。这样我就可以更好地认识社区。

参考

Knuth, DE (2005)。计算机编程艺术：第 1 卷，第 1 卷：MMIX，新千年的 RISC 计算机。新泽西州上马鞍河：Addison-Wesley。

这是一个例子：

1. [00] 2009年二进制形式...
2. [05] 哪个字母...
3. [10] 四位量——半字节或十六进制数字...
4. [15] 一千字节...
5. [M13] 如果 x 是由 0 和 1 组成的任意字符串...
6. [M20] 证明或反驳...

[00]、[05]、[10]、[15]、[M13]、[M20] 是什么意思？

我努力了：

• 谷歌搜索taocp exercises square brackets
• 在方括号内的数字中寻找模式。
  • 它们既增加又减少
  • 它们大多是但不是全部是五的倍数
  • 有M的不时出现
  • M 是唯一的前缀
  • 代码不唯一
• 谷歌搜索"the art of computer programming" exercises brackets
• 谷歌搜索"the art of computer programming" M13
  • 查看http://dl.acm.org/citation.cfm?id=1312683，其中 M 表示里程碑。
• 谷歌搜索"the art of computer programming" [00]
• 在书中寻找解释的附录
• 考虑到除了一些问题之外的 >

没运气！

在经历了这个问题之后，我尝试实现 Dancing Links 以仅解决确切的覆盖问题，以下是从这里获取并修改的代码（它是 Column-Row 结构，我需要 Row-Column 结构）。它工作正常，只是它永远不会到达Search函数中的成功终止块，我试图跟踪并发现这个

导致它。示例：对于以下矩阵

我的代码失败到cover最后一列Header=4

我该如何克服呢？这是完整的代码

我一直在阅读 Donald Knuth 的 The Art of Programming, Volume 1，其中将 MIX 用作汇编语言。在 Knuth 谈到 MIX 中的算术运算的部分中，我不明白减法、乘法和除法运算是如何进行的。

例如，教科书有这样的：

寄存器 A 具有以下字代码：-| 1234 | 0 | 0 | 9一个存储单元，例如 M，具有以下字代码：-| 2000 | 150 | 0。

书中说执行 AM 的结果是：+| 766 | 149|?.

在 MIX 中，内存被分割成单词。每个字都有以下内容： 第一个字段表示符号（+ 或 -）
接下来的两个字节保存地址。
下一个字节表示索引，而第五个字节用于字段说明。
最后一个字节用于操作码。
书中说执行 AM 的结果是：+| 766 | 149|?.

谁能帮我这个？

长话短说：1986 年，一位面试官要求 Donald Knuth 编写一个程序，该程序接受文本和数字 N 的输入，并列出按频率排序的 N 个最常用词。Knuth 制作了一个 10 页的 Pascal 程序，Douglas McIlroy 用以下 6 行 shell 脚本回复了该程序：

在http://www.leancrew.com/all-this/2011/12/more-shell-less-egg/阅读全文。

当然，他们有非常不同的目标：Knuth 展示了他的文学编程概念并从头开始构建一切，而 McIlroy 使用一些常见的 UNIX 实用程序来实现最短的源代码。

我的问题是：这有多糟糕？
（纯粹从运行时速度的角度来看，因为我很确定我们都同意 6 行代码比 10 页更容易理解/维护，不管是否有文字编程。）

我可以理解这sort -rn | sed ${1}q可能不是提取常用词的最有效方法，但是有什么问题tr -sc A-za-z '\n' | tr A-Z a-z呢？对我来说看起来很不错。关于sort | uniq -c，这是确定频率的一种非常缓慢的方法吗？

几点考虑：

• tr应该是线性时间（？）
• sort我不确定，但我假设它没那么糟糕
• uniq也应该是线性时间
• 产卵进程应该是线性时间（进程数）

我想了解 Knuth-Morris-Pratt 算法的工作原理。我从普林斯顿大学https://www.youtube.com/watch?v=iZ93Unvxwtw观看了本教程。在这个视频中，他们使用了一个表格，字母的长度 = 行数，图案的长度 = 列数。将表格视为 DFA，用于检测文本中的模式。我认为这种方法很有趣，但维基百科说 Knuth-Morris-Pratt 算法使用前缀表，前缀长度只有一行。两者都有效，并且在速度方面都是 O(n+m)（n 是文本的长度，m 是模式的长度）。但 DFA 版本需要更多空间。但问题是哪个是真正的 Knuth-Morris-Pratt 算法，哪个是微分？

我不明白 Knuth 在他对第 1.1 章练习 8 的说明中的意思。

任务是制作两个正整数的有效 gcd 算法，并m使用n他的符号theta[j],和其中 theta 和 phi 是字符串，并且- 在这种情况下代表计算步骤的正整数。phi[j]b[j]a[j]ab

让输入是表单的字符串a^mb^n。

schnaader 在这里给出了 Knuth 算法的一个很好的解释。

我的问题是，这如何与练习中给出的方向联系起来，以使用书中给出的算法 E，原始r（余数）被替换|m-n|并n替换为min(m,n)。

我正在重新实现分册 1 中的 Knuth 程序 P：生成前 500 个素数。该程序生成前 25 个素数没有问题。该代码如下：

如果将 Mthree 中的比较减少到 25，那么程序就可以了。任何更高的程序都会出现故障或在 printf 中挂起。

我正在组装它：

我还可以补充一点，在没有调用 printf 的情况下，它会成功生成前 500 个素数，这可以从在 gdb 中的“结束”处放置一个断点看出。

一旦我尝试调用 printf，它就会出错，所以我假设我对堆栈做了一些愚蠢的事情。

The original MIX architecture features 6-bit bytes and memory is addressed as 31-bit words (5 bytes and a sign bit). As a thought exercise I'm wondering how the C language can function in this environment, given:

• char has at least 8 bits (annex E of C99 spec)
• C99 spec section 6.3.2.3 ("Pointers") paragraph 8 says "When a pointer to an object is converted to a pointer to a character type, the result points to the lowest addressed byte of the object. Successive increments of the result, up to the size of the object, yield pointers to the remaining bytes of the object." My interpretation of this requirement is that it underpins "memcpy(&dst_obj, &src_obj, sizeof(src_obj))".

Approaches that I can think of:

1. Make char 31 bits, so indirection through "char*" is simple memory access. But this makes strings wasteful (and means it isn't POSIX-compliant as that apparently requires 8 bit chars)
2. Pack three 8 bit chars into one word, with 7 ignored bits: "char*" might be composed of word address and char index within it. However this seems to violate 6.3.2.3, i.e. memcpy() would necessarily skip the ignored bits (which are probably meaningful for the real object type)
3. Fully pack chars into words, e.g. the fourth 8 bit char would have 7 bits in word 0 and one bit in word 1. However this seems to require that all objects are sized in 8 bit chars, e.g. a "uint31_t" couldn't be declared to match the word length since this again has the memcpy() problem.

So that seems to leave the first (wasteful) option of using 31-bit chars with all objects sized as multiples of char - am I correct in reading it this way?