2

わかりました、私は困惑しています。TAOCP vol1、第 3 版、セクション 1.3.2「The MIX Assembly language」は、配列の最大値を見つけるための簡単なアセンブリ プログラムを提供します。プログラムは、145 ページに、各命令が実行されると思われる回数と共に示されています。次のページには、「[...] サブルーチンを実行する時間の長さ; それは (5+5n+3A)u [...] です」と書かれています。

しかし: リストに示されているカウントを実際に合計すると、係数 (4+4n+2A) になります。このような不一致は、他のアルゴリズムでも発生します。たとえば、セクション 1.3.3 のプログラム A の分析では、Knuth は「単純な加算によって [..] (7+5A+...)」と書いています。実際に「単純足し算」をすると、(5+3A+…)

ここで何が起こっているのですか？

これは、括弧内のテキストからのカウントを横に並べた MIX コードです。入力しやすいように、ラベル名を 2 文字に短縮しました

    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

OK, I figured this one out. The "u" after the factor in parentheses tipped me off: some instructions take longer to execute than others. When this is taken into consideration (there's a table with instruction timings in the book), everything checks out.

于 2012-03-17T18:22:01.163 に答える