问题标签 [taocp]

这是一个例子：

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]
• 在书中寻找解释的附录
• 考虑到除了一些问题之外的 >

没运气！

以下短语中的“lg”是什么意思？

“......当提到 M _t [ x ] 时，我们忽略了x的最低有效 lg t位。” （Knuth，2005 年，第 4-5 页）。

从上下文来看，“lg t”似乎意味着“t -1”，因此 lg 2 为 1，lg 5 为 4。也就是说，“lg”在这里的严格含义是什么？

参考

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

翻阅我的 3 卷 TAOCP，我找不到短随机序列的来源：

还有一个算法，可能还有一个 MIX 程序来验证 const 以便返回所有 2^16 值。至少那是我记得的。同样在相同的一般领域中，上述递归有效，因为 (2^16)+1 是素数，但可惜 (2^32)+1 和 (2^64)-1 都不是素数。

FWIW，将 const 替换为 iconst = 1/const (mod 0x10001) 以相反的顺序生成序列。即 const*iconst%0x10001 = 1

我不明白 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)。

我希望能够学习 MIX/MMIX，但我不知道用来编写它的工具链。我过去曾将 uVision 用于 ARM 汇编器相关的东西，MIX/MMIX 是否存在这样的等价物？

我正在尝试执行简单的整数除法（9/2=？），但 MIX builder 引发整数溢出错误。难道我做错了什么？这是代码：

在 MMIX 机器mmix-doc第 3 页第 4 段的文档中：

我们使用该符号来表示由 从 location 开始的连续字节组成的数字。（符号 表示将 k 的最低有效 t 位设置为 0，并且只保留结果地址的最低 64 位。...

我一直在阅读The Art of Computer Programming，虽然它有一些我无法理解的高等数学，但做一些练习很有趣。

在我完成其中一个之后，我会去寻找答案，看看我是否比书中建议的更好或更差（通常更糟），但我不知道我目前的答案是什么试图传达。

本书的问题和建议的解决方案可以在这里找到

我所理解的是，这t可能是“缺失”元素的数量，也可能是一个一般常数，但我真正不明白的是看似任意的指令来根据它们的组件对它们进行排序，在我看来这就像在旋转你的轮子就位，因为乍一看它不会让你更接近原始订单。以及决定（除其他外）用数字替换成对名称的一部分（文件 G 包含 n−t < i ≤ n 的所有对 (i,xi)）。

所以我的问题很简单，如何从这个答案中提取算法？

一点澄清：

我明白它的目的是什么，以及我将如何将它翻译成 C++。我不明白为什么我应该对输入文件的副本进行排序，如果是这样，我应该按照哪些标准进行排序，以及将对的一侧更改为数字的原因。

我正在阅读 Knuth 的The Art of Computer Programming，我对 MIX 汇编语言有疑问，尤其是 DIV 运算符。

在第 133 页，他给出了一个示例，说明 DIV 运算符如何影响累加器和扩展寄存器，给定这些寄存器的特定状态，以及输入存储单元。这篇 Stack Overflow 帖子描述了这个问题（我想也回答了这个问题）：MIX 中的除法如何工作？

我的问题是回答的人使用我不明白的方法将存储在 rAX（寄存器 A 和 X）中的 10 字节字的值转换为一个数字：

如果您手动进行除法，通过将字节转换为单个数字，您将得到 -210,501,825（如果您使用的是最小的字节 - 在 Knuths 书中是 6 位（！））

有人可以指导我完成这种转换吗？

谢谢，山姆

我正在阅读mysql的gen_lex_hash.cc，但我不知道解释：

提出算法的想法见 Donald E. Knuth 第 3 卷“排序和搜索”的“计算机编程艺术” （第 6.3 章“数字搜索” - 章节名称和编号 是从俄语版回译的 :)）

从上面的流程中，我无法理解细节，也找不到任何详细的解释。

为了理解这一点，我调试了程序gen_lex_hash，但它没有任何帮助，例如：

1. 0,-1意味着什么？

任何建议将被认真考虑！