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

ОК, я в тупике. 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 ответ

Решение

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

Другие вопросы по тегам