Алгоритм анализа в TAOCP - PullRequest
Новая
       42

Алгоритм анализа в TAOCP

2 голосов
/ 17 марта 2012

ОК, я в тупике. TAOCP vol1, 3-е издание, раздел 1.3.2 «Язык ассемблера MIX» предоставляет простую программу сборки для поиска максимума массива. Программа приведена на стр. 145 вместе с указанием количества выполнений каждой инструкции. На следующей странице написано: «[...] продолжительность выполнения подпрограммы; это (5 + 5n + 3A) u [...]»

НО: когда вы на самом деле суммируете числа, указанные в листинге, вы получаете коэффициент (4 + 4n + 2A). Такие расхождения встречаются и в других алгоритмах. Например, при анализе Программы A в разделе 1.3.3 Кнут пишет «простым сложением [..] (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]

1 Ответ

0 голосов
/ 17 марта 2012

ОК, я понял это. «U» после коэффициента в скобках подсказало мне: некоторые инструкции выполняются дольше, чем другие. Когда это принимается во внимание (в книге есть таблица с временами инструкций), все проверяется.

...