Алгоритм анализа в 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" после коэффициента в скобках подсказало мне: некоторые инструкции выполняются дольше, чем другие. Когда это принимается во внимание (в книге есть таблица с временами инструкций), все проверяется.