Author: Udo Wermuth Program: 1-3-3I.mms (V1, p. 177)

Program I (Inverse in place)

N IS 6 Number of elements in the permutation j IS $2 Variables of the algorithm

    i         IS        $3

mm IS $4 For m the value is multiplied by 8

              LOC       Data_Segment
    X         GREG      @

OCTA 0 X[0] is not used OCTA 6,2,1,5,4,3 The data of Table 1.3.3–3

              LOC       #100
    * Inverse a permutation in place

01 Invert SET mm,N 1 \underline{I1. Initialize.}

02  SL        mm,mm,3  1 m ← n.

03  NEG       j,1  1 j ← −1.

04 2H LDO i,X,mm N \underline{I2. Next element.} i ← X[m].

05  PBN       i,5F  N To I5 if i < 0.

06 3H STO j,X,mm N \underline{I3. Invert one.} X[m] ← j.

07  SR        j,mm,3  N

08  NEG       j,j  N j ← −m.

09  SL        mm,i,3  N m ← i.

10  LDO       i,X,mm  N i ← X[m].

11 4H PBP i,3B N \underline{I4. End of cycle?} To I3 if i > 0.

12  SET       i,j  C Otherwise set i ← j.

13 5H NEG i,i N \underline{I5. Store final value.} 14 STO i,X,mm N X[m] ← −i. 15 6H SUB mm,mm,8 N \underline{I6. Loop on m.}

16  PBP       mm,2B  N To I2 if m > 0.

    * inspect memory locations of array X for the result
              TRAP      0,Halt,0
    Main      IS        Invert

Analysis This time negation is used to tag the numbers as it is stated in the algorithm. Programs A and B used symbols not numbers.

The PB.. instructions in lines 05 and 11 are based on the assumption that C ≤ N/2. Later the analysis of C in the book shows that the assumption is correct.

The program needs 4Nμ + (12N + 5C + 5)υ. The execution with the test data gives the statistic for

Invert: 78 instructions, 24 mems, 92 oops; 11 good guesses, 7 bad. As in this case N = 6 and

C = 3 the above formula calculates 24μ and 72 + 15 + 5υ = 92υ in agreement with the measured data.

Date: 04 Jan 2012 1