Knuth MIX 划分示例

问题描述 投票:0回答:1

我在遵循 Donald Knuth 的《计算机编程艺术》(第 3 版) 中的示例时遇到了困难。 我通过开始在这里提问(“向鸭子解释一下”)来解决这个问题,所以我想我不妨把我的“问题”留在这里,以防它对其他人有帮助。

Knuth 给出了他(编造的)

DIV

 机器中的 
MIX
 操作员的示例。  在本机中,一个字节可以是 6 位(最大值 63)或 2 位数字(最大值 99)。  一个字由一个 (+/-) 符号后跟 5 个字节组成。  指令 
DIV 1000
 获取符号和寄存器 A 中的 5 个字节 (rA) 以及寄存器 X 中的 5 个字节 (rX),将它们组合成 10 字节数,然后除以位置 1000 的内容。整个部分商的值放入rA,余数放入rX。  rA 的符号设置为商的符号,rX 的符号设置为 rA 的前一个符号。  书中简单的例子是:

DIV 1000 +---+---+---+---+---+---+ | + | 0 | rA before +---+---+---+---+---+---+ | ? | 17 | rX before +---+---+---+---+---+---+ | + | 3 | Cell 1000 +---+---+---+---+---+---+ | + | 5 | rA after +---+---+---+---+---+---+ | + | 2 | rX after +---+---+---+---+---+---+
在此示例中,每组 5 个字节代表一个数字。  被除数是 0+17 = 17,除数是 3,商是 5 余 2。到目前为止一切顺利。  请注意,机器是二进制还是十进制并不重要,因为这些值是明确的。  (问号表示rX的初始符号不影响结果。)

棘手的是,rA 或 rX 中的所有字节是否都用于表示单个数字;在这种情况下,数基会影响结果,这意味着结果是不明确的。 书中的下一个例子是

DIV 1000 +---+---+---+---+---+---+ | - | 0 | rA before +---+---+---+---+---+---+ | + | 1235 | 0 | 3 | 1 | rX before +---+---+---+---+---+---+ | - | 0 | 0 | 0 | 2 | 0 | Cell 1000 +---+---+---+---+---+---+ | + | 0 | 617 | ? | ? | rA after +---+---+---+---+---+---+ | - | 0 | 0 | 0 | ? | 1 | rX after +---+---+---+---+---+---+
这里rX的字节2和3代表一个数字,但其他字节代表不同的数字。  “之后”行中的问号表示二进制和十进制机器将给出不同的结果。

为什么617是明确的,但其他值却是模糊的?

division knuth
1个回答
0
投票
如果机器是十进制,则 rX 的字节表示 1235(100^3) + 3(100) + 1 = 1,235,000,301,除数为 2(100) + 0 = 200。则商为 6,175,001 余 101,所以rA的数字字节变成6 17 50 01.

但如果机器是二进制,则rX的字节代表1235(64^3) + 3(64) + 1 = 323,748,033,除数为2(64) + 0 = 128。商为2529281余13,即可以写成 9(64^3) + 41(64^2) + 32(64) + 1,所以rA的二进制字节变成9 41 32 1。但是9(64) + 41 = 617,所以无论机器是十进制还是二进制,字节2和3都可以解释为617。 然而,较低有效字节是不同的。

同样,rX 的最后一个字节对于十进制和二进制计算都是 1:十进制计算余数为 1(100) + 1,二进制计算余数为 1。 无论哪种方式,最低有效字节都是 1。因此,rA 的字节 2-3 中的 617 和 rX 的字节 5 中的 1 无论如何都是相同的,但所有其他字节都不同,因此所有其他字节中的问号字节槽。

最新问题
© www.soinside.com 2019 - 2025. All rights reserved.