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
– Oliver Charlesworth, Commented Mar 17, 2012 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
– zvrba, Commented Mar 17, 2012 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
– Sword22, Commented Mar 17, 2012 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
– zvrba, Commented Mar 17, 2012 at 18:20

zvrba · Accepted Answer · 2012-03-17 18:22:01Z

0

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.

answered Mar 17, 2012 at 18:22

zvrba

24.7k3 gold badges57 silver badges66 bronze badges

Sign up to request clarification or add additional context in comments.

Collectives™ on Stack Overflow

Algorithm analysis in TAOCP

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related