问题标签 [taocp]

我正在学习 MMIX，所以我尝试制作一个简单的程序来添加一个并打印结果。不幸的是它不打印任何东西。这是我的程序：

我究竟做错了什么？

我决定阅读 Donald Knuth 爵士的“计算机编程艺术”系列。

根据您的经验，请建议从哪一卷开始比较好，如更容易的一卷（相对于其他卷），并且请建议您阅读后续卷的首选顺序。

我并不急于学习这一切，所以任何类型的音量都应该适合我开始。

我正在尝试在区间 [0,1] 中实现一个高斯分布的随机数生成器。

这几乎是 Knuth 的 TAOCP 第 3 版第 122 页的第 2 卷中算法的直接实现。

问题是rand_gauss()有时会返回区间 [0,1] 之外的值。

经典的算法书籍（TAOCP、CLR）（以及不那么经典的书籍，例如fxtbook）都充满了命令式算法。这对于其实现主要基于数组的算法最为明显，例如组合生成（在算法中同时使用数组索引和数组值）或联合查找算法。

这些算法的最坏情况复杂性分析取决于数组访问为 O(1)。如果你用类似数组的持久结构替换数组，比如 Clojure 所做的，数组访问不再是 O(1)，并且这些算法的复杂性分析不再有效。

这让我想到了以下问题：纯函数式编程与经典算法文献不兼容吗？

在计算机编程艺术中，在第 485 页的底部

假设有一棵m阶B树，有N个key，那么N+1个叶子出现在第l层。

级别 1,2,3... 上的节点数至少为 2,2[m/2],2[m/2]^2...

（这里 [] 表示上限）

和 Knuth 给

N+1 >= 2[m/2]^(l-1)

我的问题是：

这不应该是 N+1 >= 2+2[m/2]+2[m/2]^2+...+2[m/2]^(l-1) 吗？

只考虑第 (l-1) 级的节点有什么意义？

好吧，我难住了。TAOCP vol1，第 3 版，第 1.3.2 节“MIX 汇编语言”提供了一个简单的汇编程序，用于查找数组的最大值。该程序在第 145 页上给出，以及每条指令应该执行的次数。在下一页它说“[...] 执行子程序的时间长度；它是 (5+5n+3A)u [...]”

但是：当您实际将列表中给出的计数相加时，您最终会得到 (4+4n+2A) 的因子。这种差异也出现在其他算法中。例如，在第 1.3.3 节对程序 A 的分析中，Knuth 写道“通过简单的加法 [..] (7+5A+...)”。当您实际执行“简单加法”时，您最终会得到 (5+3A+...)

这里发生了什么？

这是 MIX 代码，其中并排括号中的文本计数。为了便于输入，我将标签名称缩短为两个字符

我正在阅读 Knuth 的书 TAOCP。我只是在学习一个简单的寄存器数学运算。还有一个减法运算的例子：

我知道 -1234-(-2000) = 766 但如何 (0 | 0) - 150 = 149 ??

为什么 9 - 0 = ？

这些是“包装”的话。也许我需要阅读更多关于他们的信息。或者谁能​​解释一下？

In 1.2.1 Mathematical Induction section, Knuth presents mathematical induction as a two steps process to prove that P(n) is true for all positive integers n:

a) Give a proof that P(1) is true;

b) Give a proof that "if all P(1), P(2),..., P(n) are true, then P(n+1) is also true";

I have serious doubt about that. Indeed, I believe that point b) should be:

b) Give a proof that "if P(n) is true, then P(n+1) is also true". The major difference here is that you are only assuming that P(n) is true, not P(n-1), etc.

However, these books are old and have been read by many people (most of them being much more clever than I am^^).

So what is my confusion here?

我一直在阅读 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。