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

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

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

источник

2012-03-17 zvrba

Вы хотите добавить код, соответствующий вашему примеру? –

ok, я добавил список кодов для нахождения максимума. Программа A довольно длинная (~ 80 LOC), поэтому я ее не буду вводить. – zvrba

Поскольку вы не даете никаких сведений о том, что «A» и «n», я могу только догадываться. Некоторые инструкции в сборке принимают более или менее циклы в зависимости от ситуации (например, для условного перехода). Это может быть ответ (возможно, книга дает худший случай). Другая возможность заключается в том, что, может быть, книга (которая, как я не знаю), содержит некоторые специальные соглашения относительно длины времени. – Sword22

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

источник

2012-03-17 18:22:01 zvrba

ответ

Смежные вопросы