2

好吧，我难住了。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 代码，其中并排括号中的文本计数。为了便于输入，我将标签名称缩短为两个字符

    X EQU 1000
      ORIG 3000
MA    STJ EX      [1]
IN    ENT3 0,1    [1]
      JMP CH      [1]
LO    CMPA X,3    [n-1]
      JGE *+3     [n-1]
CH    ENT2 0,3    [A+1]
      LDA X,3     [A+1]
      DEC3 1      [n]
      J3P LO      [n]
EX    JMP *       [1]
4

1 回答 1

0

好的，我想通了这一点。括号中的因素后面的“u”告诉我：有些指令的执行时间比其他指令要长。当考虑到这一点时（书中有一张包含指令时间的表格），一切都会检查出来。

于 2012-03-17T18:22:01.163 回答