Algorithm analysis in TAOCP

Question

OK, I'm stumped. TAOCP vol1, 3rd edition, section 1.3.2 "The MIX Assembly language" gives a simple assembly program for finding the maximum of an array. The program is given on page 145 together with the number of times each instruction is supposedly executed. On the next page it says "[...] the length of time to perform the subroutine; it is (5+5n+3A)u [...]"

BUT: When you actually sum the counts given in the listing, you end up with the factor of (4+4n+2A). Such discrepancies occur also in other algorithms. For example, in the analysis of Program A in section 1.3.3 Knuth writes "by simple addition [..] (7+5A+...)". When you actually perform the "simple addition", you end up with (5+3A+...)

What is going on here?

here's the MIX code with counts from the text in brackets by side. I have shortened label-names to two characters for ease of typing

    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]

Would you care to add the code corresponding to your example? — Oliver Charlesworth, Mar 17 '12 at 14:10
ok, I have added the code listing for finding the maximum. Program A is rather long (~ 80 LOC), so I won't type it. — zvrba, Mar 17 '12 at 14:19
As you don't give any informations on what "A" and "n" are I can only guess. Some instructions in assembly take more or less cycles depending on the situation (for a conditional jump for exemple). That may be the answer (maybe the book gives the worst case). The other possibility is that maybe the book (which I don't know) has some special conventions regarding the time lengths. — Sword22, Mar 17 '12 at 18:05
@Sword22 It doesn't really matter what A and n are; just parameters. You are correct, I have just figured it out myself: some instructions take longer time to execute than others; the "u" after the factor in parentheses tipped me off. I multiplied everything also by the number of time units each instruction takes, and everything checks out now. And it's nowhere explained in the text, grrr. — zvrba, Mar 17 '12 at 18:20

score 0 · Accepted Answer · answered Mar 17 '12 at 18:22

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.

Algorithm analysis in TAOCP

1 Answers1